Ages ago there has been quite a long discussion on this board about what language you should expose yourself to, while learning the basics. In my opinion the two basic schools that crystalized out of this were a) keeping yourself as far away from the machine (the specifics of the computer) you are working on as possible ( the arguement here is that you first need to get a grasp of the basic algroithms, that are important, instead of being directly confronted with the limitations of a particular machine you are working on ). Classical languages to start out programming with here would be Scheme (Check out the MIT introductory stuff on this... http://mitpress.mit.edu/sicp/full-text/book/book.html) or other lisp dialects. Python, Ruby or Smalltalk are popular examples as well. When I first went to university this was the standard way of teaching programming. Moto: Start out with the abstract and go down from there.
Good books : The MIT one I mentioned... and http://www.gigamonkeys.com/book/, which is a nice intro to LISP
The other way would be b). I hardly know anyone on the web who hasn't taken this aproach. Of course I can't speak for everyone, but my motivation for getting into programming was, that I got interested in how to create games on a certain platform. Like I owned an Amiga 500, when I was young and moved from playing games on it to writing them (I rented books form the local library on programming... Today I would be extremely surprised to find any books on programming in a school library... My first original programming effort was on an 286... I had recently moved from my Amiga to the PC because of XWing and other titles. In short, the PC started to become an atractive platfrom, as Comodore began to go the way of the Dodo). In this case picking a language that exposes some amount of the underlying system to you can be very helpful. C/C++ today is probably the prime example here (Not because it's a good language... it isn't (*moveflameproofunderwearinposition*)... but because a lot of people are familiar with it and there is more information out there than for any other language). The main didactic experience here would be that you will be confronted with stuff that is neatly hidden away in more abstract languages, like being able to directly access the piece of memory your program works on.
By starting out pretty much at the metal like this (at least that's the theory), you will get a pretty good feeling for what your computer actually does when running a program you write.
Good books on c/c++ : http://www.amazon.com/C%2B%2B-Programming-Language-Special-3rd/dp/0201700735/ref=pd\_bbs\_sr\_1/104-5356416-5161553?ie=UTF8&s=books&qid=1182918696&sr=8-1
One thing to take away from any discussion about programming languages is that they all share a crucial aspect of equality, in that they are all able to perform the same computations. In that respect it might be the best idea to look at a few languages and pick whatever you feel most comfortable with.
edit: The c++ books i proposed are actually quite bad, since they are more or less advanced. A good idea would be to check out your local Barne's and Noble's (or whatever shop your local mall features) and browse through the introductory books they have in stock.