And I'd have to disagree with Nick. Don't start with C, as it is imho, one of the ugliest and less esthetically pleasing languages out there. When you start off, you don't want to go too "low level".
It's just as "esthetical" as C++. The implementation part of C++ is still totally C. And if you refer to the habit they had to use short variable names, many underscores and meaningless abbreviations, that has nothing to do with the language. You can perfectly write elegant C code.
And I believe you absolutely have to start as 'low level' as possible. At my university, the primary programming language is Java. It's a good language, but not for beginners. They understand absolutely nothing about programming after their first few lessons. I've known students who, after a full semester, still didn't fully understand execution flow. Syntax errors were their worst nightmare.
In my opinion, the first programming lesson should be in assembly. This sounds crazy, but really isn't. Teaching someone how add, mov, jmp, etc. works isn't harder than using a pocket calculator. They will instantly understand execution flow and even pointers. You don't have to teach anything about advanced instructions or complex addressing. Just one or two hours (practical excercises) is sufficient. Give the students a simplified list of what the basic instructions do.
Stepping to C is really easy then, it's just like using the basic assembly instructions, but with expressions that look like mathematical formulas, that are executed one operation at a time. They will appreciate C's features, and understand syntax requirements. It's also the perfect time to let them look at the (debug) assembly output. They will instantly understand what a compiler really is, and how to debug an expression if the C debugger doesn't give them enough information.
Then you can step to C++. Execution flow is harder to understand here, but you can teach them how it saves you from some tasks, and how to organize data and functions in classes. Again they will appreciate every new feature, and won't fear the syntax. They will instantly understand that constructors/destructors are just like regular C functions, but implicitely called by the compiler, they will understand that virtual functions are just function pointers.
They would simply know how things work, instead of thinking of Java as some magical language spoken by all processors. Working bottom-to-top will keep them excited to learn new things, and they'll never ask how something can be broken up into simpler steps they can understand, they'll already know. Trust me, everybody I know who became a good C++/Java programmer in a short time, started with a very 'low level' language.