The Little Schemer - It's not about the Scheme language at all, it's about teaching recursive thinking. Once you "get it", it changes the way you think about programming.
Code by Charles Petzold - Explains how computers work by starting with Boolean arithmetic and working towards RAM and video cards. Short read, but essential in today's throw-away culture.
Don't Make Me Think - I've bought this book 3 times, every time someone borrows it they keep it. Essential if you are doing ANY kind of UI or UX work.
Test-Driven Development: By Example - Nice and practical. Resolves a lot of the questions that surround TDD like "How much should I test?" and "What should I test?". Shows how TDD is less about the tests and more about the design of your code.
Writing Secure Code (2nd Edition) - You won't work for me or with me if you don't own this unless there is a threat involved.
Clean Code - Robert Martin - An excellent book for learning to recognize bad software.
Working Effectively with Legacy Code - Michael Feathers - Useful refactoring techniques combined with useful testing patterns. As a programmer, new or veteran, most of your time will be spent working on code you didn't write.