Godel, Escher, Bach is a brilliant book. Now, Douglas R. Hofstadter, has just released a new book, I Am a Strange Loop, a must read.

Other interesting books:

The Computational Beauty of Nature, of Gary Flake. Flake was in NEC labs, then Yahoo research and he is now Director of Microsoft Live Labs.

The Quark and the Jaguar, written by the nobel laureate Murray Gell-Mann. A nice video of one of his tallks from Google Eng Series.