Oof. Just have them read
Numerical Recipes while you're at it. Knuth is great, but it's
dense, even when you discount the use of MIX.
Definitely take a look at SICP (http://mitpress.mit.edu/sicp/full-text/book/book.html) and the related HTDP (http://www.ccs.neu.edu/home/matthias/HtDP2e/) -- both will require you to get used to Scheme (it's good for you!), but will expose you to the underlying theory of how to compute, which is critical.
Before those two, you could also start with O'Reilly's "Understanding Computation," which is a bit more Ruby-centric than I prefer, but a non-rigorous take on the same subjects. Petzold's "Code" is also a good, non-specialist place to start. (Petzold's "Annotated Turing" is great, but I'd leave it for a while.)
You should read the "Schemer" series (Little, Seasoned, Reasoned) -- again, lots of Scheme, but wonderful if somewhat idiosyncratic reads.
Going back in time, Wirth's "Algorithms + Data Structures = Programs" is a classic in the field, and a pleasure to read.
CLRS' "Intro. to Algorithms" is a foundational text on algorithm analysis and design, though you might also want to try some of the more popular treatments first (O'Reilly has a few good ones). See also Skiena's "Algorithm Design Manual."
The "Dragon Book" (Compilers: Principles, Techniques, and Tools) by Aho, Sethi and Ullman is on every computer scientist's bookshelf for good reason -- it tells you everything you need to know about how the languages you use are built. I also like Holub's "Compiler Design in C," though it's a lot more hands-on.
For understanding OSes, I recommend "The Magic Garden Explained," and Bach's "Design of the UNIX Operating System." Outdated, perhaps, but outstanding in their clarity.
C (yes, you should learn C; like Lisp, it's also good for you even if you only use it rarely): King's "C Programming: A Modern Approach" (though you could start with a popular introduction like O'Reilly's "Head First C"), Plauger's "Standard C Library," Hanson's "C Interfaces and Implementations," and O'Reilly's "Understanding and Using C Pointers," as a start. Van der Linden's "Expert C Programming" is an excellent intermediate text that is also surprisingly readable.
Architecture and design miscellanea: Kernighan's "Practice of Programming," Bentley's "Programming Pearls," McConnell's "Code Complete," and Hunt and Thomas' "Pragmatic Programmer."
I have not yet read, but intend to, Okasaki's "Purely Functional Data Structures."
Make a habit of browsing second-hand bookstores and picking up older computer science books -- they cover by necessity much more foundational issues than most modern books, and do so using simpler architectures and languages. (I have a wonderful text on 68008 programming that has absolutely no practical relevance to the current age, but provides fantastic insights into the nuts and bolts of hardware and OS development.) As a bonus, you'll see how few ideas in computer science are truly new -- as computational bottlenecks shift, theoretical technologies suddenly become practical, or practical ones become outmoded.