Wow, can't wait for the unknown gems this discussion will bring up!

Anyway, some of my own; these are all non-fiction.

• Richard Dawkins' The Selfish Gene is such a magnificent book, introducing all the wonderful solutions that evolution has come up with, and the insight that the battle for the 'survival of the fittest' takes place at the level of individual genes (or is at least a powerful model for understanding things)
• Jared Diamonds' Guns, germs and steel which suggests that there are non-racial/non-ethnic reasons for the differences in wealth and power amongst various regions in the world. I think the writer's claims go a bit further than his evidence warrants, but nevertheless a good way to look into this field, and provides a lot of food for thought
• As mentioned already, Hofstadters Gödel/Escher/Bach and The Mind's I (bundle of essays of various writers, redacted together with Daniel Dennett) are playing with all these interesting concepts like conciousness, AI, meta, self-reference.
• Also Richard Feynman's work is fantastic -- the auto-biographic (You must be joking, Mr. Feynman and What do you care what other people think) are inspiring. I plan on going through some of his real physics works (like the Feynman lectures on Physics). Just seeing some of the interviews on Youtube show how well Feynman is able to make both complex and simple things understandable, at all levels; such a towering intellect.
• For computer science stuff, earlier I mentioned SICP, which I am currently re-reading.
• Then, Knuth's The Art of Computer Programming; I have read much too little of it, but it's such a rewarding experience to (slowly!) go through a few pages and finally the 'click' of understanding. I plan to read more of this. Knuth is truly the master of the field of programming and algorithms, and while reading it, I can almost feel how it sharpens my brain.
• Finally, a lot of bad things can be said about pop-psy, but I really liked Dan Ariely's books (Predictably irrational and The upside of irrationality) that show where the classical picture of people being rational, homo economicus, has its limitations, and all the weird biases we have. He has some interesting TED-talks as well.