I'd be the last to claim I've swum a majority of the book lagoon, but I have found over the years that the majority of programming books are neither timeless nor all that well-written. Pascal's response seems obvious, in retrospect: if I could start it all over, what would I read?
In Pascal's case, I'd recommend The Structure and Interpretation of Computer Programs. As a Math teacher, he should find the calculus-based examples in the early chapters relatively easy -- if not downright intuitive. SICP is easily the richest and most thoughtful programming book I've ever read. Were it not for all the math it assumed familiar to the reader, I'd recommend it to everyone above and beyond all other texts in the discipline.
For everyone else (myself included), I'd put The Little Schemer at the top of the list, quickly followed by The Seasoned Schemer and The Reasoned Schemer. The books are a joy to read thanks to their peculiar style and between them convey many of the ideas SICP presents as a more traditional academic text.
Why not Learn to Program or Learn Java in 21 Days?
Most introductory programming books and online tutorials (even Why the Lucky Stiff's Poignant Guide to Ruby, in all its humour and beauty) make a grave mistake in their introduction to programming: They misrepresent syntax as the first principle of writing code.
If the first chapter of your introductory literature explains the representation of strings and numbers in [insert-your-language-of-choice-here], you've already started your reader off on the wrong foot. Worse yet, there's a temptation to teach new programmers about variables, mutation of state, and side-effects -- such as printing to the console.
One does not require dozens of books and years of practice to understand the essence of writing software. But in my case, it took as much to unlearn the bad habits taught by my first texts.
