I don't know enough about non-Lisp languages to recommend one.
If I knew them well enough to choose one, my pick would be whatever makes it easiest to write simple programs. Building confidence is the most important thing, not conceptual elegance. I wrote most of my first programs in old fashioned Basic. It was a kludge of a language, but it was good for writing the dumb little programs I started with. The worry that people will form bad habits from using ugly languages is overblown.
JavaScript probably fails miserably on the "easiest to write simple programs" count.
The development environment is easy to find, obviously...any browser and any plain text editor. But user interaction is hard, and gets all mixed up with nasty DOM and browser incompatibilities in short order. You also have to have additional tools (like Firebug) to get anything resembling useful errors from JavaScript.
A good modern learning language probably ought to have an interactive shell. Ruby, Python, Scheme, and Smalltalk are probably all good choices. JavaScript can have an interactive shell in the form of FireBug...but again, it's scary when you get to doing anything that interacts with the user and very few tutorials of JavaScript cover interacting with JavaScript interactively. Having the knobs do something immediately when you twiddle them is almost certain to speed up the learning process. The human mind is pretty good at abstract reasoning: "flipping this light switch causes the light to come on over there". But the more you separate things out temporally and the more variables involved the less they stick: "flipping this light switch starts a timer, which depending on the current state of the light, will cause it to turn on or off in three minutes".
Merely being a non-compiled language is still a slower iterative process than direct interaction (which is the primary disqualifying point against Perl as a learning language in my opinion...corrected in Perl 6, of course, but that's still a few months out). The shorter the "try, debug, try again" cycle is the faster one picks things up, I think. I found Ruby very fast to learn, to some degree, for that reason. Python was almost as discoverable, though I found it less intuitive, where "intuitive" is probably defined as "kinda like what I'm used to". PLT Scheme was a pretty cool learning experience, but it became less interesting as soon as I wanted to build something useful with it--so few libraries (of course, as a Perl user, I feel that way about every language other than Perl...CPAN spoils you for all other languages when it comes to "just get it working" prototyping).
We don't really need the browser's implementation of Javascript. For example, consider Steve Yegge's rails port to JS which he developed on top of Rhino (the mozilla engine.) IIRC, rhino includes a very basic shell.
Ah, but then you have to have a JVM, so "having Rhino" is a challenge. But I guess if you're not on a UNIX system where Perl, Python and Ruby are pervasive and always available (or a couple of clicks or commands away), then having Java around is just the same amount of effort. It also lacks "beginner" tutorials that are focused on the kind of interaction that you need to understand to build applications. JavaScript is a weird interactive model, because you are talking to the DOM to do anything interesting, which is a mess--it's really way more complex than beginners usually grasp (I have a hard time with it, and I've been developing in several languages since I was a kid).
That said, I think in the end JavaScript is going to be the world's most popular language for almost everything, including web applications. I happen to agree with Yegge in that regard. But it's still somewhat less friendly to learners than the other languages I mentioned.
Anyway, if Rhino (or some other standalone JavaScript engine) becomes popular I'd reckon that in a year there will be some good tutorials for interactive JavaScript, and it'll become a great choice for learning programming. I happen to think JavaScript is a very pretty language. A few confusing quirks (Function vs. function vs. = {}(); modules, for example), but overall it offers some great functionality in a pretty simple syntax and low keyword manner.
Scheme worked wonderfully for me on this criteria. Even if it looks scary, as a newbie, I felt I knew what the interpreter was doing. This built my confidence much more than putting a lot of power in my hands that I didn't understand, like some other languages I tried first.
Scheme is awesome as long as you are mathematically fearless enough to learn from square one using books like How to Design Programs and The Structure and Interpretation of Computer Programs. They provide a great foundation if you feel right at home in math, and you're not too concerned with building something practical for your first project.
For people who aren't as confident in their math, I would recommend Python, as other have mentioned. It's thoroughly friendly to newcomers, there's tons of good documentation (the free tutorial written by Guido is incredible), the libraries are among the best available, and, like Scheme, it's easy to start by biting off a manageable chunk and then gradually learning more details as you go.
