First, my school started us with a course in theory (sets, counting, probability, recurrences). Only second semester did we start programming (and continue with theory: regular, context-free languages, turing machines). This is the track offered to "honors cs" students which, officially, display "significant interest in CS" but may easily have no programming experience. I don't know if this is a better model, but it certainly worked much better for those of us that would eventually have gotten it anyway.

Now we get to the part where I sound like an asshole:

I'm not convinced that there is a good argument for teaching the "normal" students. In math, we don't go out of our way to attract people that don't like or aren't good at math. In fact, they usually come to us and say "I'm terrible at math" or "I hate math" and we politely help them with the calculus they need to pass to graduate and send them on their way. Math seems to have accepted its position as a "higher discipline" and while there are those that lament its inaccessibility to the layman, they don't lament that there are so few laymen in class---they just want to be able to show pretty girls at the bar pictures of the beautiful structures they play with all day.

So why can't CS just accept that some people just "don't get" the discipline? It is really hard, you have have a really amazingly large amount of domain knowledge, going all the way up from the metal to the OS and libraries, plus you have to know all this discrete math, understand algorithms of many flavors from many sub-disciplines, and recall it all at once so you can make tradeoffs. A good deal of the theory comes damn close to the math people are so open about being terrible at.

The way computer science works, you get students that love the math and can handle the programming, that stick with it long enough to excel with the programming too, and do great. Then, you get students that love the programming and can handle the math, same thing happens. But right now, you also get the students that hate the math and admit it, and hate the programming but don't feel like they can admit it, so they stick with it until they either drop to Information Science or something, or they graduate and become another one of those programmers that recruiters are always implicitly complaining about when they say "it's so hard to find good programmers".

In math, students who aren't excellent and passionate generally don't even try, or don't continue. That's because all they can do with a bachelor's in math is go to grad school, where they have to be good. In CS, it seems like we think we can send off crappy graduates and, well, if they can't go to grad school, at least they can get jobs programming. Well, wake up. Industry doesn't want them either. Better to help these kids realize they don't like the field and find something they do like, than let them continue busting their asses believing they'll get their dream job just for graduating.

This doesn't mean we should turn people away after the first semester. I like this model: let the kids that are really good skip the intro class(es), and make the intro classes intro classes. This means taking care to think about just how little background you can assume (in particular, assume no math skills, because otherwise they'd probably be math majors). Let this sequence take a year or so if necessary. Redesign the upper-division curriculum to both leave time for this extra intro stuff, and to take advantage of it: don't waste space with "upper-division" classes that are really just there for the crappy students to take so they can have something to do, because you won't have those students anymore. That way, you still be able to serve the average students, but they'll be nurtured at the right pace, making up for the lack of education in high school, until they're ready (or realize it's not for them), which seems to me like a much better model than "sink-or-swim CS 1".