I'd also recommend (inter alia -- there's a lot of great works out there!) Friedman et al.'s Schemer books, Petzold's "Code" and "The Annotated Turing," McConnell's "Code Complete," Pierce's "Types and Programming Languages," and Warren's "Hacker's Delight."
- The C Programming Language (original C book)
- The Art of Computer Programming (TAOCP)
- Structure and Interpretation of Computer Programs (SICP)
- Compilers: Principles, Techniques, and Tools (Dragon book)
- Don't Make Me Think (design)
- Zen and the Art of Motorcycle Maintenance