I really believe we should be educating middle and high school kids about how to use computers for more than the internet and document processing. Given the way computers and the internet are everywhere and are used for so much, computer use / programming / scripting should be a required class like history and science are.
There is only one solution to letting more people do more things with computers: make things easier. Things that were once impossible are now incredibly easy for a lot of people, because interfaces are getting better all the time. That's the way to get more people comfortable with computers, not forcing them to spend time learning a skill they're not going to learn anyway.
And as a nice side bonus, making interfaces easier to use ends up saving everyone time, even people who are technically inclined, and makes much cooler things possible. So everyone comes out a winner.
But you can do the equivalent of that if you're programming literate. We're moving to a digital culture, and if you don't know how to program you'll increasingly only become a consumer of other people's solutions, without the ability to solve your own problems.
Some people are calling this "procedural literacy".
As an aside I'd argue that computer interfaces have actually gotten somewhat worse while getting more friendly to newcomers. I think the last major leap in computer interfaces was cron(1). Unlike most modern interfaces being produced today you can use it to tell your computer to produce periodic reports and things like that.
That's where we should be headed with UI's, not aiming to have a monkey banging at the terminal at all times, but giving the monkey the ability to dictate things to the computer so he doesn't have to bang at the terminal.
Real computing power is being able to say: "Computer, I'm feeling under the weather today and I think I'll sleep in. At 9am please start playing 'Daddy's sick, get up and go to school!' on a loop in the kid's bedroom at 75 dB, and continue producing noise until they get out the door, engage!".
You can implement those sorts of things if you're a programmer.
I think it's deeply wrong to try and raise procedural awareness by forcing the technicalities of state of the art programming on the common man. You should find a way to teach algorithmic principles so that they are generally applicable.
The best way to teach people procedural awareness is probably to teach people to tinker with something they can start using right away.
Things like automatically programming your phone to reply to your parents via SMS with some plausible responses when you're out drinking, use the Facebook API to get info about your friends that they thought wasn't accessible etc. Show how you can use rtmpdump to download your favorite music from some closed video site, or write a script for uTorrent that'll have downloaded your favorite TV episode by the time you wake up.
The most important thing is to show people that procedural awareness will be worthwhile for them in their everyday life. It's easy to demonstrate that, and it's actually true for most people, unlike other some other subjects at school which'll probably never be pertinent to the average student.
Make knowledge acquisition both a) fun and b) timely. Add a motivating situation that leads people to want/need to learn, and they will.
I think mechanics class should totally be required. I'm often amazed that we force children to study subjects like geography or physics, that are important but only if you're interested in them and not terribly practical anyway.
I think all children should have to learn basic life skills to enable them to control their physical and social environment ('hack' in the context of this article). Subjects such as driving, mechanics, basic electronics, law, small business, tax, nutrition, rhetoric, negotiation, plumbing etc. etc. And those just off the top of my head.
All 'academic' subjects should merely be introduced and then left up to the student to choose to pursue. What on earth is the point of filling children's heads full of history (for example) if they aren't interested? They forget every word of it a year after their final exam anyway.
I think you're right that at the moment it's more than what almost all everyday users need, but the trend is definitely towards it being something that most people could learn/would benefit greatly from learning. So then the problem is identifying when that transition happens; perhaps it's already happening in some fields such as the one described in the article.
So half would be centered around epistemic/instrumental rationality and science, and another half is engineering.