You could also try something different, and try a language based on the functional paradigm, like SML or Haskell. They are very different from the imperative languages that are used most in the industry (like Java and C#), although functional languages are getting more popular (F#, Scala).

I think they have some benefits as first languages. First of all, not very many people have tried programming in a functional style, which means that students who may have some experience with programming won't get bored.
Second, when you have learned the syntax (which is actually pretty minimal and well-defined), this way of programming is pretty intuitive I think.

Functional languages may seem very weird at first, because some of the well-known imperative elements doesn't exist. You don't have any kind of loops for instance, all iterations are made using recursion. You don't have state either, so you can't change the contents of a value when it's been set. But when you've learned programming the style, it suddenly makes a lot of sense!

-Ulrik

Python seems to be the teaching language of the moment.

If you want to go this route you might check out:

How to Think Like a Computer Scientist
Learning with Python at:

http://www.ibiblio.org/obp/thinkCSpy/

Ken