Implementations and libraries are a drawback. I think the best way to learn a language is to build something interesting using it, and the only thing that's easy to build with Javascript these days is the client-side part of a website. Doing that also requires CSS and HTML, which the OP should probably learn a bit about, but it might be distracting to do that while he's trying to learn the fundamentals of programming. Trying to learn Emacs at the same time I was learning Lisp was distracting for me. I don't think browser incompatibilities are a reason to shun JS; unless you're building something for a website used by the general public, just target Firefox. Use Firebug to learn what's going on with your code and track down problems. Once you know what you're doing, it's more tedious than difficult to get it working on other browsers.
If you already know how to make web pages, or really want to learn, JS is probably a good choice. If not, it probably isn't. It's probably best to can figure out what sort of project you'd like to build, and then learn a language well-suited to building it.
It's possible to use Javascript for other purposes, but it's not yet easy. In a couple years, that might change - Steve Yegge seems to think it's the "next big language".
For a first language, look at Python/Ruby and choose what you're most comfortable with.
I happened to listen to a talk Marc Andreessen did called , "2005: A Web Odyssey" <http://osc.gigavox.com/shows/detail994.html>; where Andreessen talks about commodity hardware and how it effects programming language choice.
"... programming has moved from being machine dependent and complicated to become a dynamic and easy-to-learn process ..."
Andreessen talks about how languages are moving up the ladder from machine languages to "high level, dynamic languages" by looking at increasingly comoditised, powerful hardware. He notes that Java should now be thought of as a system language. JS in browsers was created in '95 to bridge the gap b/w HTML & Java. Java was deemed too complicated for HTML users. The original idea was JS to be server side. But it never took off due to lack of effort by Netscape to create an Open source version and the tool problems.
"PHP is to 2005 what Java is to 1995"
A lot of the talk he talks about how "PHP is to 2005 what Java is to 1995" The talk was done in 2005. So for Andressen PHP or PHP like languages (Ruby, Python etc) are what he suggests. But right near the end of the talk he talks about Sajax and JPSpan where server side PHP (python,perl) transparently talks to higher level JS code in the browser.
You can find more about Sajax and JPSpan following:
And, as the learner makes progress, he can start to go deep into the functional side of the language.
It seems to be a nice fit for the case, indeed. Python would be my second best.
I was also introduced to OO (of sorts) through JS... I perhaps wouldn't recommend this so much, it was incredibly confusing for me at first. I didn't have any real grounding in OO principles before I started though, so perhaps that would have helped.
I think most people starting out with Javascript would learn how to do stuff in a browser but not how to "program".
Functional JS rocks. And the fact that you can examine other peoples' programs with FireBug is huge.
On the other side, using only Javascript with a stand-alone interpreter would be a nice.
I would go for Logo.
[edit: a couple of spelling mistake]
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.
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).
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.
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.