I second this, although I am not finished with it, I can say it is a very interesting read. Thanks for the link to the author's site which has lecture notes, I didn't know this existed. The lecture notes are easy going an have a good sense of humor, such as the following:
"It's a shame that, after proving his Completeness Theorem, Gödel never really did anything else of note. [Pause for comic effect] "
This would be my recommendation as well. It is closer to a textbook, than say a popular science book, but is still a very fun, engaging, and at times pretty funny read.
Similarly to books like GEB, it really exposed me to a whole range of fascinating ideas and topics that I am now interested in.
A brilliant MIT professor's reflections on the intersection between computer science, physics and philosophy.
Here are the lecture notes and book: http://www.scottaaronson.com/democritus/
I also very much recommend the author's blog: http://www.scottaaronson.com/blog/