My limited teaching experienced was based on these points:

• What I'm trying to teach is problem solving. Programming language is a tool to accomplish this task.
• Fundamentals are what I call linguistic constructions (loops, if-then-else, data structures and so on).
• Solutions are expressed in pseudo-code, which I describe as a midpoint between natural and artificial language. So they can solve problem even if they think they can't program.
• First, let students try to solve their problem with linguistic constructions they learned so far. Perhaps the problem is subtly stated to be hard to solve. Then, teach new constructions, that make problem easier to solve. This way, in my opinion, things are better understood and remembered.

In order to follow such points, programming language must be very simple. Translating from pseudo-code to a programming language is supposed to be seen as the simplest of the phases. Perl is sintactically too complex. Pascal is a tradition, and is close to what students will learn next years (but, of course, has a lot of limits). As I said, I'd like to use Python.
I think we actually agree :).