Non-Fiction
Proofs and Refutations by Imre Lakatos, seconding JoshuaZ's recommendation
Science and Hypothesis, The Value of Science, and Science and Method by Henri Poincare
The Tristan Chord: Wagner and Philosophy by Bryan Magee
Journey through Genius and Euler: The Master of Us All by William Dunham
The Book of Numbers by John H. Conway and Richard Guy
Fiction:
The Solitude of Prime Numbers by Paolo Giordano
Never Let Me Go and An Artist of the Floating World by Kazuo Ishiguro
Contact by Carl Sagan
Niels Lyhne by Jens Peters Jacobsen
Notes From Underground by Fyodor Dostoevsky
Songmaster by Orson Scott Card
I have Notes from Underground, but haven't yet read it. Would you tell me what impressed you in it?
This is a place to consolidate book recommendations.
I'm reading The Logic of Failure and enjoying it quite a bit. I wasn't sure whether I'd heard of it here, and I found a post here called Great Books of Failure, an article which hadn't crossed my path before.
There's a recent thread about books for a gifted young teen and a slightly less recent discussion of books on cogsci thread which might or might not be found by someone looking for good books.
So, what books or lists of books do you recommend?