I've been teaching programming to non-CS students at Stanford for the past month...they're all clearly smarter than me. But what they lack, as does virtually every non-programmer I've worked with, is the ability to (initially) understand a for-loop.

It's not that they don't get that there is such a thing as a "loop", or that a task can be broken up into iterations...they just don't know what it means to design something that can iterate across a collection and, for each member of that collection, perform a task on it. It's not merely not understanding the syntax, or the overall result...it's not comprehending that you can design and control such a thing.

I've worked with non-programming professionals in which I've taken a repetitive task, such as extracting a bit of text from each page of thousands of pages of documents, and boiled it down to a program that saves them days of work. The effect of such a program is greatly appreciated...but time and time again, these non-programmers are delighted/astounded when I perform the same task in another scenario...what bothers me is all the times when I'm not there to recognize how such a problem can be abstracted, and they dive in head first into a meaningless, repetitive chore.

The abstraction of a task, so that it can be performed in a loop...it's so fundamental that once you've done it, it's hard not to think in those terms. And I wish it were the case that very intelligent people could just get it, in the same way that those who've never played an instrument can at least appreciate Mozart. But I just haven't seen it...we programmers take for granted the ability to think in this profound way, and even though it's fairly basic, as far as ComSci education goes, it really is a gamechanger in all areas of life and work. This is why I think programming deserves consideration as a kind of literacy.

Edit: To focus on something from the OP:

> We don't want a generation of people forced to care about Unicode and UI toolkits. We want a generation of writers, biologists, and accountants that can leverage computers.

Well, sure, if you boil coding down to "Unicode" and front-end web development, then yes, it's not "literacy". In the same way that if I boiled down traditional literacy to iambic pentameter and the debate between prescriptive and descriptive linguistics, I could make a compelling case for not learning to read and write.

Edit 2: I'm willing to consider programming as not a new literacy, but "just" a branch of math...but math practiced in a pragmatic, visceral way, not in the tepid, abstract way that it is forced upon us in primary school. I do think that programming is math, but with programming, you are actively building and testing something using the principles of math. If there's a way to teach that kind of math without programming, I'm game for it.