Godel, Escher, Bach
The book deals with the way things can be studied at several different levels - a mathematical proof may be just marks on a piece of paper, but it shows the reader that something is true. If there is interaction between different levels then this can lead to weird results. But this is all done in such a playful way that it makes even highly abstract ideas accessible to a wide readership. There are plenty of conversations between Achilles and the tortoise, as well as several of their guests (including the author himself). The book is now available as a 20th anniversary edition, and for this a new preface has been added but the main text of the book has been left as it was - Hofstadter explains in the preface why attempting to make any changes would have lead to writing a new book. (I felt he ought to have sneaked a request into the original text, supposedly from his younger self asking that his older self didn't make any revisions).
I think Gödel has the upper hand in this book - there are interesting ideas on music and art, but Escher and Bach tend to play the role of supporting characters. Hofstadter also explains in the preface some of his 'strange loop' ideas on the nature of the mind, which also tended to get hidden in the original book.
I didn't actually read Gödel, Escher, Bach until some time after it had been published, and I realised after I'd read it that I should have done so much earlier. There's no doubt about it - if you are interested in the puzzles and paradoxes of self-reference then this book is a must read.