Structure and Interpretation of Computer Programs http://mitpress.mit.edu/sicp/full-text/book/book.html

It is one of the classic CS textbooks still used by Berkeley (CS61A) and MIT (not sure) intro CS courses. Its not trivial stuff. While it wont teach you obscure data structures like ropes, it will expose you to a wide variety of topics including but not limited to: functional programming, lambda calculus, OOP, logic programming, client/server programming, non deterministic programming, streams as data, the meta-circular evaluator, lazy evaluation, and concurrency. I had a fairly strong CS background before taking CS61A at Berkeley, but this book (thanks to Scheme) taught me how beautiful computer science can be. Now working in Java is a complete turn off ;)