Introduction to Algorithms by Cormen et al. (I've read about halfway through this, excellent reference, not so good of a starting point).
Structure and Interpretation of Computer Programs (SICP) by Abelson et al. - Available for free (legally) right here
Algorithm Design Manual by Skiena - A much better starting point than "Introduction to Algorithms"; very useful, too.
The C Programming Language by Kernigham and Ritchie - A perfect model of what a programming language tutorial should look like
Learn You a Haskell for Great Good by Miran Lipovača - Written in an entertaining fashion, the illustrations are quite nice and explanations are awesome. Available for free (legally) here
Impatient Perl by Greg London - Teaches you Perl in a couple of hours so you start hacking together scripts, available here
Problem Solving Strategies by Arthur Engel - Absolutely amazing book with a great collection of mathematical puzzles
Anything by Martin Gardner - Almost always a fun and entertaining read for anyone
Linear Algebra by Gilbert Strang - Very conversational textbook about Linear Algebra
Principles of Mathematical Analysis by Walter Rudin - A classic, very clear explanations, great proofs
Fermat's Enigma by Simon Singh - A very entertaining read about Fermat's Last Theorem, but, if you're looking for something technical, this definitely isn't it