Those are two of the "pure" approaches, and recently there's a third one, something in the ML/Haskell orbit. C for the low-level/machine-oriented approach, Scheme for the lambda-calculus-esque approach, and ML/Haskell for the type-theory-oriented approach.

Whether the Scheme approach is the best theoretical introduction depends on part on how important you think type systems are to modern CS. Much of PLs thinks the answer is "very important", since they view types as the basis of rigorously specifying program behavior. Rob Harper has taken that view at CMU, for example, using Standard ML in his revamped intro course. (I'm not strongly opinionated on that subject myself.)

I think the best introduction would be Scheme (to learn algorithms), assembly language (to learn machines), and then C (to unite the two). After that, I would recommend some strongly-typed language like Haskell or OCaml. And finally Python to actually get work done. :)

My friend said that UC Berkeley's undergraduate CS program followed this introduction. (In the 1990s, at least; I don't know about now.)

I think the case could be made for either C or Scheme because they are both quite small languages compared to most of the pl that are in common use. I've seen people start with something like C++ and they spend more time playing language lawyers than learn about algorithms and data structure.

The benefit of Scheme over C is that people are less likely to have experienced it before university/college. We were taught Java and C/C++ in CS, but the problem was that many people already knew them, so you ended up with a situation where half the students were bored and the other half had no idea what the lecturer was talking about.

I think Scheme is the way to go because it's very easy to build a real compiler for it and introduce assembly that way (see http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf if you don't believe me).