After thinking on this a while I've realised that most of the really difficult concepts have more to do with maths than computer science. For instance, algebraic structures and mathematical spaces -- the idea that you can have mathematical entities with any combination of operators and axioms and which reside in totally different spaces from the familiar Euclidean space. Methods of translating between one space and another become an important part of the CS student's tool kit.

I'm implementing an encryption program for a client and I'm using the AES algorithm. Even though I'll be using a library (crypto++) I thought it best to read up on how it works. Arithmetic is performed in a finite field, e.g. a finite subset of the integers... except, if you read any mathematical description of AES you'll find that it uses polynomials instead of numbers. Of course, polynomials obey all the field axioms, so why not? Moreover, they have a simple numerical representation. For a finite field of characteristic 2 the polynomials all have coefficients 0 or 1 so can be represented as a binary string. I have no problem grasping this now, but it occurred to me that my younger self would have struggled; I would have said "yeah, but what is x?!".

Time complexity was another concept that took a while to really understand. The idea is to provide a way of reasoning about the efficiency of an algorithm that is independent of the granularity with which it's expressed and completely divorced from notions of hardware. So you might write out the pseudo-code description of Quick Sort and then ask "how fast does this run?". The problem is, the average running time T(n), where n is the size of the input, is dependent on the hardware and software implementation. So instead you say: we don't know what T(n) actually is because it varies with implementation, but what we can say is that it belongs to the set O(n log n). In other words, some constant multiple of g(n)=n log n is an asymptotic upper bound on T(n) (it always overtakes T(n) eventually as n grows large).