Natural language is the bread and butter of our every day existence, and it is a veritable swiss cheese of logic. Most people won't hear your argument and notice the unfounded assumption that destroys the whole thing, but a compiler will. Most people won't notice if you leave some of what you say implicit, but your compiler will.
Something I've noticed over the years is that people, in general, are just not good at logic. Very few things teach it, the few that explicitly cover it like symbolic and formal logic classes are arcane, scary corners of the educational system. Logic doesn't win arguments, it doesn't get you laid, it generally doesn't help you interact with other people. It does teach you to think, but like deodorant, nobody knows they need it until they already have it.
So, start small. Teach logic, teach people to think, teach them the very fundamental underpinnings of programming. Programming is then just another way for people to express what they already know, like learning a foreign language rather than learning language in the first place.
I think most people saying "teach them to program!", at least the ones I've seen calling out the "it teaches you a new way to think" part, actually mean logic in general.