I've been thinking of posting something along these lines for a while and was prompted to do it by the latest "Best PHP Book?" thread.
First, what makes a programming book? I would say the fundamental aspect is that a programming book is one for which you learn a language in order to read the book, you do not read the book in order to learn a language. The latter are syntax books. Put another way, programming books teach concepts, not languages. Programming books either assume that you know the language in question, are written in pseudo-code, or they use a language so simple that you can learn it as you go without problem. SICP (see below) uses the last approach.
There are four programming books that I've seen mentioned as the greatest programming books ever. I'm sure there are many more, but these are the ones I know of. I've only really read and worked with the first one.
The Structure and Interpretation of Computer Programs by Abelson and Sussman, often mentioned as SICP. The examples and exercises in this book are written in Scheme, a dialect of LISP, because Scheme has a very simple syntax, yet is one of the most powerful languages around. Among other things, it has "lambda functions [mitpress.mit.edu]", essentially functions that have no name and can, in fact, be written on the fly and passed to other functions as arguments. The book has long been used as the first "computer science" course for students at MIT and Berkeley where it is assumed that most incoming CS majors have several years of programming under their belts. This book focusses on generalizing functions, abstracting data and functions and other general concepts on how to approach a programming problem. It's the only one of the four that I mention that I actually own and have worked through. The entire book is available online [mitpress.mit.edu] and I highly recommend checking it out.
Design Patterns by Erich Gamma, Richard Helm, Ralph Johnson, John Vlissides, the so-called "Gang of Four Book [en.wikipedia.org]". Not counting Christopher Alexander's A Pattern Language (which I have read and is really about architecture), this is the progenitor of the Patterns movement. Examples in C++ and Smalltalk (the first OO language AFAIK).
The Art of Computer Programming [en.wikipedia.org] by Donald Knuth. Named one of the twelve best books of the 20th century by American Scientist. Examples written in the hypothetical language MIX Assembly Language (for which free emulators exist). This is mostly a collection of computing algorithms.
Code Complete Second Edition by Steve McConnell is often bandied about as well as one of the best books on software development. This book, in its second edition, uses C++ and Java in the examples. Only selected chapters are available online [cc2e.com] as well as the table of contents and a few things like that.
Do any of you swear by any or all of these? I think SCIP is a *great* book that taught me a lot, but I honestly can't compare it to the others.
Are any titles missing that absolutely need to be on such a list? Remember, this list is about books that teach concepts, not languages.