For me, it depends on what you're teaching: to program, or about programming. In teaching to program, there is a huge class of languages (including C/C++, Java, C#, Python, Ruby, etc.) which offer variations on the same experience (mutable state, strict evaluation, etc., etc.). I'd like to think that my pedagogy will be more important in teaching my students to program than the tools we use.

When teaching about programming, on the other hand, I think that there are significantly fewer options. Depending on the school, many of the students won't have any experience with code that isn't imperative/OO. If you're going to teach about programming (an introduction to PL theory, for example) then you either need an extremely rigourous and flexible language, or you need lots and lots of languages. For me, I'd choose to go with Haskell (though Scheme [witness: SICP, the Reasoned Schemer, etc.] and CL will be able to handle all of the same techniques and content, just with much reduced safety, and Oz is perfect for such an approach [witness: van Roy and Haridi, 2004. Concepts Techniques and Models of Computer Programming.]) for the sole reason of monads. Implementing imperative, OO, non-deterministic, and logic programming yourself really helps get to grips with their intricacies. Furthermore, many students won't have used a language with a strong type system before (no, C/C++, Java, etc. don't count); the main reason people rail against type-checking is that their only experience is of Java's rather pathetic type system. Algebraic data-types, pattern matching, type-classes, and type inference give a much more compelling case for type-checking than anything from the C/C++, Java, etc. world.

To link this back to the original question, I don't see why the first case (teaching to program) and the second (teaching about programming) must necessarily be distinct. I plan to try a "fundamentals" approach to teaching programming (in Haskell) next year if I can get a good set-up and presentation figured out in time.