Far more readable than the usual text (Cormen), the first half is a guide on how to select and design algorithms for the problems you encounter, and the second half is a whistle-stop tour of hundreds of well-known algorithms. The tour helped me a lot with X->Y esque issues where I was building bad solutions because I didn't know anything better could exist.
Incidentally, there's a lot more to CS theory than algorithms and data structures, but if you're asking on HN for a generic CS theory book, I reckon it's most likely an algorithms and data structures book that you're after.
"Introduction to Algorithms" by CLRS seems to be the default choice, and it seems to me to be a step in the right direction (based on the TOC).
I would also like to second your point that CS is more than algorithms and data structures. I feel Dijkstra would not approve of thinking about CS as "that thing you do after learning a programming language".
Personally I'd use Cormen as "dictionary" to get into detail of stuff I first read in A.D.M.