Computer Books
If in doubt, buy O'Reilly. For reference material, their "in a Nutshell" series is second to none. If you want a more wordy tome, then the "Definitive Guide" series is excellent. O'Reilly create books with an athletic physique - full of power, and no fatty flab. Avoid bloated, overweight 1000+ page monsters. Its quality that matters, not quantity.
Having praised O'Reilly books, it is surprising that my two most influential computer books are both from Addison Wesley. Perhaps there's a lesson there.
Design Patterns, Gamma Helm Johnson Vlissides (aka Gang of Four)
One aim of object oriented programming was to get rid of decades of spaghetti code. Design Patterns takes us to the next level of quality code. I recommend every object oriented programmer to read this book. If you've got a copy of this book in your office, there's an extra benefit - you can make references to it inside javadocs. This makes the documentation easier to read for the advanced programmer (by eliminating explanation of how the design pattern works), and also more informative for the beginner (because they are directed to a full explanation of the design pattern).
Refactoring, Fowler
If Design Patterns tell us what our code should look like, then Refactoring tell us how to get there. Since reading this book, I routinely create automated test scripts, which not only makes me more efficient, it also leads to a higher quality product (because bug get caught more easily). Oh, how I regret those years where I considered test scripts a burden.
Popular Science Books
The Selfish Gene, Richard Dawkins
You may know what evolution means, you may have heard of Dawin's Origin of Species, but unless you've read The Selfish Gene, you probably don't know as much as you think.
Free (as in freedom) Books
O'Reilly publish many books with an open licence. See their Open Books Project.
Wiki Books continue the goal of free on-line information. Wiki Books is an offshoot of Wikipedia - the free on-line encyclopedia. Like most wikis, everybody is free to join in.
One benefit of this form of license, is it makes it easier to keep a book alive. If the original author loses interest while there is still interest in the community, the community can continue to make updates.