Introductions to Set Theory, Logic, etc.
From the online Stanford Encyclopedia:Introductory books on set theory and logic:
Paul Halmos' Naive Set Theory, Springer (excellent introduction to naive set theory)
A. G. Hamilton. Logic for Mathematicians, Cambridge. Good introduction to logic.
Nagel/Newman. Gödel's Proof, NY University Press. Exposition of Gödel's result.
Banach Tarski Paradox
History and Philosophy
Recreational
Rudy Rucker's White Light (or What is Cantor's Continuum Problem). Novel about Cantor's cardinals.
Any book by Raymond Smullyan, for example "What's the name of this book", "Alice in Puzzleland", etc.