Generally speaking, CS programs out there seem to lack both depth and breadth, be out of touch/time with "the desert of the real", and suffer from what Dijkstra called "the infantilization of curriculum". Too often do I see people who are proficient (for some value of "proficiency") in one (1) language, usually the wrong one. I believe that a CS program ought to introduce you to several languages, to a level where you can read and write programs of small to medium size (~1 kloc). At a minimum, in this day and age I would expect C, your least favorite mainstream language (though I personally would avoid Java, due to combination of a lack of an explicit reference type and a misguided OO fetish), something from the Lisp family (Scheme), and Javascript. Something from the ML family would be a bonus, though I would skip type theory altogether. Having been exposed to several radically different languages helps. I would ask everyone to write an interpreter for a simple language (in a language of your choice): something with variables, conditionals and function calls. A compiler for the same would be a nice next step. As projects go, this would be sufficiently involved to address Dijkstra's complaint part of the way.
A few people said something to the effect "the real world is missing". It's true. Majority of CS programs appear to be years out of date with respect to the industry practice, whatever "the industry" happens to mean for you personally. To some extent this is inevitable, though we could be doing a lot more to address the issue - say, as someone suggested, via a separate course, one that is updated biannually. A course like this could and should include a discussion of things like source control tools, build tools, etc. Things like resource management idioms in languages of the day should be discussed explicitly: too often graduates of CS programs assume infinite resources or automagical cleanup, especially if they come from a background in languages that are garbage collected. A course in parallel programming presented via different languages and their approaches to parallelism would be fantastically useful; I would pay money to see it on OCW or similar.
Somewhat related to Dijkstra's complaint is the following concern: people are terribly bad at thinking about complexity, at all levels - from a single source file to a system composed of hundreds of separate processes. We would do well to discuss managing complexity explicitly in CS curriculum: to make people think about difficulty of maintenance, changes to a working system, rollout procedures for uptime, etc. A seminar on the subject of complexity management, from small to large scale, with examples, would be very useful.
Incidentally, this is something I have been thinking a lot about over the last two years, in part due to conducting a metric shitload of interviews for intro positions. There are things that my CS program was missing, and things that a majority of programs out there seem to be missing; understandably, what I can say mostly applies to the former.