
Diagonalization and Self-Reference is the single book I would recommend the most to the HN crowd. There are a few sections on quotation and Quines that I've found endlessly useful, his 'Elementary Formal Systems' is my favorite presentation of computability, and there's a lot of really deep stuff in there about the interaction between incompleteness, uncomputability, and fixed-points.
Also, Logical Labyrinths is a pretty great textbook on formal logic. The first half is in the form of one of his puzzle books, introducing notions and building intuitions, while the second half builds off of them to provide a more formal perspective, while incidentally giving a kind of eye opening look at how he comes up with his puzzles and how they map to certain deeper properties of logic.
Down and Out in the Magic Kingdom by Cory Doctorow -- frankly, I found it kind of boring, and also found the narrator unsympathetic. I'm not sure if the author intended him to be an Unreliable Narrator or not.
Facts, Values, and Norms by Peter Railton -- Gains three stars for combining serious consideration of ethical and meta-ethical issues with a completely naturalistic worldview and a genuine grappling with history and ideology. Loses two stars for being far, far too long-winded and using vague, colloquial terminology and appeals to intuition where a methodoological naturalist can and should appeal to the fruits of science. (Copy-pasta'd from my Amazon review)
Rapture of the Nerds by Charles Stross -- pretty funny, even if it made a transhuman superintelligent supercivilization look kind of... dumb.
Currently re-reading for fun:
The Wee Free Men and I Shall Wear Midnight by Terry Pratchett -- It's Discworld. Go read them. NOW. And read A Hat Full of Sky in the middle.
Then there's been a lot of textbooks I've been reading, which I won't list. Though...
Logical Labyrinths by Raymond Smullyan -- dense, and fun, a graduate-level intro textbook to first-order logic disguised as a logic textbook.