Can anyone else recommend a book like this that discusses paradoxes and how they relate to philosophical questions?
I liked Poundstone’s “Prisoner’s Dillema” too, so don’t mention that one.
You might take a look at What is the Name of This Book? by Raymond Smullyan, an puzzle-oriented look at Gödel’s work.