Object-Oriented Common Lisp - Despite the title, this is really a general
introduction to CL. It was one of the books I used to learn Lisp and I still
think it is a good text for learning CL.
The Seasoned Schemer - Takes "The Little Schemer" further in teaching you
to "think about computing".
Artificial Intelligence: A Modern Approach - The ultimate AI book! Takes
an agent-oriented approach throughout the book to introduce different AI
techniques. Once you've read PAIP and decided that you're still interested in
AI, this book is the one to read.
Genetic Programming: Vols I,
II &
III - The first is the best book on Genetic Programming, Volume II adds
ADF's (Automatically Defined Functions). Volume III is mostly just a series of
case studies.
Godel, Escher, Bach: An Eternal Golden Braid - I loved this book when I
first read it. The first copy I bought still sits on my bookshelf, having
survived moves from New Zealand to Western Samoa to Boulder.