GEB is another one that will change how you see the world. I'd never recommend it, though, unless someone was willing to read it over the course of the year. I say that about a lot of things these days, but that one really is true.

Well, it's true for anyone other than the most obsessive and fixated, who might be able to read it faster. For sort-of-normal people, though, it's basically the Gravity's Rainbow of theoretical computer science / computational philosophy.