You may hate me for this, but I'd recommend e-lisp.
Why? It's got many of the advantages of scheme, and it's a language that'll treat you well the rest of your programming career (assuming you continue to use emacs).
Also, the immediate feedback and lots of example source is pretty nice.
1. Virtually no syntax, which is often problematic to first time programmers of C-style languages: "You mean I have to have this curly brace here, and this semicolon there?"
2. Only one choice for looping, recursion. Recursion is a fundamental concept in computer science and programming, yet many people do not grasp it. Scheme learning materials will teach you how to write recursive programs the right way. Plus, recursion is a very elegant, and easy to understand way to express many algorithms such as those used in sorting, a common exercise when learning programming.
3. Higher order functions - This makes it easy to teach abstraction. Build small components that do general things (i.e. fold, map, filter). This sort of thing applies to OOP down the road, as well as to every other paradigm. Break things into small units that do one or two things and that's it.
4. Unbounded numeric tower, which means you don't have to focus on things like, "ints can only express up to 2^32 if they are unsigned," which in many courses has to be taught (prematurely, I'd say) to explain why I can't compile or run a program that multiplies the largest numbers I can type. Something the curious will surely try first.
Yeah they are all good, but the syntax while more concise is actually more difficult to map to a non programming mindset.
Objects in their very naive form area pretty straightforward concept to get (Oh a Car is a type of Vehicle).
Iteration is more natural than recursion (I prefer recursion, it's elegant, but it's not how people think to start with).
And most users won't run into the boundaries of variables when beginning learning either.
The one thing I will give credit is that the syntax is less voodoo, but I still think the ideas of assignment and a mental model of state combined with the imperative "Do this" approach is easier for non-programmers to understand.
