I'd agree that C is a solid foundation to learn on, and also that assembly can really add a few ripples to the old grey wad. Scheme and Lisp dialects are good because they make you realize that TI(truly)MTOWTDE(verything)

I found though that the course in college that really, profoundly, changed my programming approach was a course in state machines and finite automata (with a nice segueway into regular expressions, of course) - these being the absolute foundations and primordial soup of computer science, I suppose this is natural, don't overlook this significance. Ensure that they recieve these lessons.