Simon Peyton Jones gave a great lecture on this topic at Strange Loop a few years ago. Basically, "computer science" can be reframed as the study of information, computation and communication. Thinking about these subjects rigorously and solving the problems surrounding them is a foundational skill that is much more broadly applicable than just in programming, and really does not need to involve computers at all (as he shows in his lecture.
> I could be totally wrong, but I've never seen an instance where kids exposed to dumbed-down "reduced complexity" material outperform those that weren't, except in sports and art.
I'm not sure I follow. I mean, that's how children learn to read and write, it is not? Or how they learn maths at school: one step at a time.