I would recommend Gödel, Escher, Bach by Douglas Hofstadter if you haven't already read it.
But in hindsight, its value to me was not in the content of the book, as much as in communicating the kind of delight and curiosity around programming that has kept me interested in the subject since 1972 or so.
Other books have done the same thing for me, most notably everything by Martin Gardner, Raymond Smullyan's books about logic puzzles that sneak an education past you, and William Poundstone's books about Game Theory and Computability.
In a way, I'm delighted that this book is not sitting as the number one thread so far. Not because it's terrible, but because new generations ahve written great books, and they deserve mention too.
To me, the most interesting thing about programming is what it teaches us about our own minds. It's a little like being an archeologist and finding collections of pottery, houses, &c. but no people. You make deductions about how they lived from their tools.
In our case, we have only a limited ability to directly examine the workings of our brains, but a wealth of ways to study the things we do with our brains, including the making of tools for our brains to use.
Programming is one of those tools, and its study is indirectly the study of us.
At the end of the day, it's all just 1s and 0s, but when we argue about whether the Visitor Pattern addresses the Expression problem, and so forth, we're indirectly exploring the (metaphorical) shape of our brains.
I have just said in several paragraphs what Michael Fellows said in one sentence: "Computer science is not about machines, in the same way that astronomy is not about telescopes."
They may have been thinking about mathematics, but I am thinking about people.
Another amazing book of his that I don't see mentioned a lot (perhaps because it is more technical that maybe any of his other books) is 'Fluid Concepts And Creative Analogies'.
I'm reading that one now. I recommend it, along with Perception as Analogy by Melanie Mitchell, and the aforementioned Godel, Escher, Bach to anyone interested in AI / cognitive science. I've only read a small part of Metamagical Themas to date, but I've read enough to recommend that as well. Just the stuff on self-referential sentences makes it worth reading.
;)
Did I get everything out of it that Hofstadter intended to put in? Almost certainly not, but I still got quite a bit of out it, IMO. And I can always go back and re-read it.