>>joelg+(OP)
One of my earliest exposures to CS was his Computation: Finite and Infinite Machines.
"Communication with Alien Intelligence" is another favorite of mine. The idea of enumerating all possible Turing Machines and looking for ones that do something meaningful is brilliant.