If you make programming a math class, people will hate it just the same way they hate math.
Bringing Python or R in to graph the meaningless functions that we graphed on our TI-83s doesn't add much value - what you are doing is still pointless. If you want to teach high-school-level pre-calculus, I think the best bet would be to offer a 3D graphics course. Jamming math into people's heads without showing them why it would ever be useful is about as effective as jamming a camel through the eye of a needle. You've got to trick people into learning math.
> You've got to trick people into learning math
That's the one I'm opposed to because everyone has different preferences, so this tricking is incompatible with the one to many approach in industrialized education.
On the other hand, I completely agree that the lack of application is often a drag and game-programming was my favorite application, but I did that on my own time and it wouldn't have been fun if I was mandated to do so.
Also, purity in maths is motivated by the variability of applications. Purity is an ideal, of course, but it's one about keeping it simple, which is nice.
As I was saying in the OP, the applications should be individually obvious and hence voluntary. If that could be incorporated into class, that would be great, but the reality looks different. Of course my experience is biased.
Teach them CS first.
Start with the history. Make a connection from maths to CS - Logic. Show that representation is meaning. The Code is only an abstraction but it is the only way to communicate the abstract ideas, never mind there's different forms of code. Try to code to understand complexity, that the complexity is the reason that "Programming" is bigger than school. I don't mean run-time complexity, but that is an important bit.
The code is just one of the real-world applications of programming, it's secondary to problem solving, but useful enough at that. It's well enough defined in the mathematical sense to be taught as a formally structured, rigorous generality (Theory). It's highly developed and abstract enough to go a long way with intuition applied to immediate problems (Practice). Recurse, apply code to code. Dont' forget the disciplined mantras: RTFM, KISS DRY ...
Preferably it shouldn't even be a single class. Just like everyone has to learn about numbers, matter, elements or cells, it should be important to teach logic as the very basis on the search for boolean truth. Tie in self modifying code with evolution.
Instead of just introducing calculators in math, introduce python, Matlab, R, all of them at appropriate times. As a prime example of applied CS that's relevant to about any teenager with a smartphone, explain the graph theory that they are the data in.
It all depends on the children being on an appropriate level already when they enter elementary school. That depends on the knowledge of the previous generation. Therefore it's a slow progress, that picks up every iteration. There generally isn't a one size fits all program to teach programming, it depends on individual parameters. The ideal OTOH is very narrow minded and far from optimal, given many more pressing needs. Biology is booming, isn't it? Should we ask the same question in Bio, how to teach non-Bio folks to do research? It's coming along, the only hindrence I see is dangerous half knowledge and knowing to much.