One of my all-time favourite computer science textbooks is Structure and Interpretation of Computer Programs, which is the textbook accompanying the equally named introductory CS course at MIT. The course gives an introduction to programming, program design and how programming languages work.

This is not an average programming course: Topics covered are a range of different programming models like functional programming, logic programming, data-directed programming (OO is a specialization of that) as well as stream-oriented programming.

I read this book pretty late in my studies, and it still lead to an amazingly large number of "Aha" moments. One of my favourite ones is the example which motivates procedural abstraction (first-class functions). It also contains insightful discussions of layered system design and a number of interpreters are built for different Scheme dialects, including one with lazy evaluation and one with ambiguous values. Finally, its last chapter discusses how to implement (dynamically typed, garbage collected) languages on register machines (real processors).

It is an ever-ongoing discussion whether this book it suited for beginners. Amazon's review page contains some very strong opinions in both directions. While I can't judge this, I can definitely recommend having a look at the lecture content in text or video form, because it's available free of charge: :-)

• http://mitpress.mit.edu/sicp/ — Book website, including full text in HTML format
• http://groups.csail.mit.edu/mac/classes/6.001/abelson-sussman-lectures/ — Video lectures (highly recommended and often very entertaining!)
• Wikipedia has a more complete and up-to-date list of links on SICP.