I'm going to, *with some reservation*, recommend the book Godel, Escher, and Bach, by Douglas Hofstadter. Anyone with a low tolerance for whimsy, silliness, and general opacity will probably want to avoid this book (the last time I mentioned this book to someone who was a regular on this forum he described it as "extremely annoying"). It deals with the three title figures (especially Godel's Incompleteness Theorems), of course, but covers a very broad array of subjects: formal systems and logic, programming, Zen, semiotics and language, and, especially but rather circuitously, AI and cognitive science. Can be in turns amusing and enlightening.
_________________
* here for the nachos.