But I agree with your suggestion that C should be teached first. If anything, because C's "computational model" is very simple: you know what executes when; it encourages a more common, procedural way of thinking, and it's easy to do side effects in single-threaded C.
Dana S. Scott. Outline of a mathematical theory of computation. Technical Monograph PRG-2, Oxford University Computing Laboratory, Oxford, England, November 1970.
Dana Scott and Christopher Strachey. Toward a mathematical semantics for computer languages Oxford Programming Research Group Technical Monograph. PRG-6. 1971.
Gordon D. Plotkin. A Structural Approach to Operational Semantics. (1981) Tech. Rep. DAIMI FN-19, Computer Science Department, Aarhus University, Aarhus, Denmark
Intro to programming books:
Matthias Felleisen, Robert Bruce Findler, Matthew Flatt, and Shriram Krishnamurthi. How to Design Programs: An Introduction to Programming and Computing.
Daniel P. Friedman (Author), Matthias Felleisen (Author), Duane Bibby (Drawings), Gerald J. Sussman (Foreword). The Little Schemer.
Programming language principles & implementation books:
Daniel P. Friedman, Mitchell Wand, and Christopher T. Haynes. Essentials of Programming Languages.
Shriram Krishnamurthi. Programming Languages: Application and Interpretation.
Matthias Felleisen, Robby Findler, and Matthew Flatt. Semantics Engineering with PLT Redex
These are all by pretty much the same group of people (but distributed across the US: http://racket-lang.org/people.html) so the books all go together really well.
I agree that C++ is a complicated language, specially when you use Boost or Tools.h++, or the even make things worse. But when you teach beginners to code in C++ and only utilize STL, I believe it would be an interesting and challenging course. Plus, in an entry level course, you only need to introduce the basics of programming, which are (in an abstract sense) general logic principles and language agnostic.
I agree that you need to teach general logic principles which are language agnostic, but if you do this in the context of C++, the beginner is bound to waste a lot of his time fighting irrelevancies in the language.
So I'm skeptical of the idea that programming education needs to be even more hardcore than Scheme and we need to use a lazy functional language instead. I think the right way to teach programming is to give students a simple procedural language (perhaps not even OO) that makes the computer do cool things, like graphics or webpages. The ones who are curious for more hardcore stuff can always discover it afterward, like I did.