I thought a bit about Google's Go. It gets rid of the preprocessor and cleans up handling of pointers. But it also does away with manual memory management. That may be getting too far away from the machine for learning purposes.
I also thought about Ada, but that seems to impose a heavy learning overhead.
What about going the other direction, down to assembly? Unlike many people, I have no loathing of assembly programming. I find well-structured and commented assembly code to be just as easy to read as similar quality C code. Although it has a reputation for being hard, experienced ASM coders tell me it's just a matter a familiarity. They claim to be just as productive in ASM as in C.
My decision to pass over assembly is because modern processors no longer have a straightforwardly sequential execution model. The image you get from tracing assembly code is only an approximation of what will happen in the processor, which is the same as you can say for C code. So my perception is that there is no particular benefit to knowing ASM any more. (Unless you are working with older, simpler designs as in embedded systems.)