Computer Science is a pretty broad area of study, but I consider these three problems to be the most fundamental.

Computability: What can a computer do and what can it not do? There are an uncountably infinite number of problems that a computer cannot solve (undecidable), and only a countably infinite number of problems that a computer can solve (decidable). Fortunately, most of the interesting problems are decidable.

Complexity: If a computer can do something, how efficiently can it be done? This goes beyond the Big O you are taught as an undergraduate, and considered language spaces such as P, NP, PSPACE, EXPTIME, and so on. It also considered not only computation time but space (unfortunately, few undergraduates are introduced to space constraints of algorithms, a great interview question is to list an example of a sorting algorithm that takes constant space).

Equivalence: Given two algorithms, do they perform the same computation? Meaning that given the same inputs they will always produce the same outputs (and yes, side effects are also outputs)? A less strict (but of more practical importance) is whether or not a program meets a specification.

Computability and complexity are both important parts of the theory of computation, which is usually built on top of Language Theory, which is itself built on top of Set Theory. The hardest problem is modern mathematics may be P = NP, which is also a Computer Science problem. The third problem requires creating mathematical proofs using Formal Logic. It is also an excellent example of an undecidable problem, meaning that there is no general algorithm that can perform it for every program (in other words, it's something that a computer cannot do).

In addition to Set Theory and Formal Logic, Computer Science relies heavily on Boolean Algebra, Graph Theory, and other areas of Discrete Mathematics. Computer Science is inherently cross-disciplinary, but at its core it is closer to Mathematics than it is to Engineering or Science.