No mention of SICP - the CS classic that's not only decently rigorous, but actually inspires the fun and joy of programming, as it promises in its Preface:
That said, I'd also suggest:
* Concepts, Techniques, and Models of Computer Programming by Peter Van-Roy and Seif Haridi ("CTM"), which covers several different programming approaches. Not about different languages, but their underlying models, and ways in which they can be combined.
* The Art of Prolog, by Sterling & Shapiro - An excellent book on logic programming, using Prolog for exercises. (CTM also touches on Prolog, but this book goes quite a bit deeper.)
* The Lambda papers - http://library.readscheme.org/page1.html
* _Lisp in Small Pieces_ by Christian Queinnec ("LiSP"). On implementing Lisp, strongly skewed towards Scheme.
* Paradigms of Artificial Intelligence Programming by Peter Norvig ("PAIP"). AI, problem solving techniques, Lisp practicalities and implementation, Prolog, tons more. Extremely lucid. (I wish it was a hardcover, though.)
* C Interfaces & Implementations by David Hanson - an excellent book on how to design C library APIs, including quite a few useful libraries.
(the greater shame, of course, is that these people are less likely to find a satisfying job in the area than their seemingly uninterested CS-grad friends (grumble grumble))
If PAIP doesn't get you into data-driven programming, _The Art of Prolog_ definitely will.
Prolog and Natural-Language Analysis, Fernando C. N. Pereira and Stuart M. Shieber
Clocksin's _Clause and Effect_ would definitely be the _Little Schemer_ of Prolog. (No elephants or PB&J, though.)