I used Data Abstraction and Problem Solving with Java by Carrano and Prichard for 2 terms and found it to be a solid book that is rigorous and interesting. A Head FIrst Data Structures book would rock!
"Computer science is no more about computers than astronomy is about telescopes" - Edsger Dijkstra
+1 for "Introduction to algorithms" by Corman/Leiserson/Rivest. It covers lots of interesting topics, and explains them very well. It has pseudocode, no ready-to-tun programs, but I consider that to be a good thing.