Python is certainly a good one (ruby as well) - "Learning Python" by Lutz & Ascher I think is suitable for someone like you (and it is not a bad reference as you get more experienced). Ruby can be a bit stranger, people like to be "clever" in ruby, and then there is the hype.
As for mind expanding, I like scheme - as taught by MIT in the SICP series (you can watch the videos on google video). It would be interesting to see that taught to someone new to programming (sorry to make an experiment of you !).
As for practical messy stuff, then look into Java (for basic static strong typing and endless tools), Perl if you must.
Another angle: Haskell seems to be popular for functional programming (as it is pure) - many people think functional's time has come, and there are some useful videos introducing it here: http://sequence.complete.org/hwn/20070807
Stick to things where you can get all the tools you need for free on the platform you use (and they are easy to get running).
Alright, as much as I love Haskell, do not attempt to learn it as a first language. Repeat: do not attempt to learn it as a first language. That's like learning to swim by taking a submarine into the Marianas Trench and then opening the airlock.
I wonder if Haskell is as hard for first-time programmers as for experienced ones, though. There are high school kids in #haskell that know way more and probably have an easier time learning than I did. They don't have any bad habits to unlearn.
Also, many "tricky" Haskell concepts (algebraic data types, lexical closures, first-class functions, programming without state) are actually quite logical if you've never been exposed to the C/Java way of programming.
I don't agree that exposure has anything to do with it. Its like saying being a viola player makes it harder to pick up the guitar (as you are tranposing strings/notes in your head). Yeah for about the first day it may be a bit strange but once you get past that it is not a problem.
Miranda was the first language I ever learnt. I am the only person who I know who learned a strict functional language from the get go. And yes, it scared and confused the heck out of me :( I am not sure if it helps, but at least I (only now) have a appreciation for the mathematical side of functions/functional programming (has taken me 10 years to get here though).
The highschoolers on #haskell have some unusual activity going on upstairs. I knew ihope from userfriendly.org before I came to #haskell, and always assumed he was a grad student somewhere. I literally fell out of my chair when I found out that he was 13 years old.
As for mind expanding, I like scheme - as taught by MIT in the SICP series (you can watch the videos on google video). It would be interesting to see that taught to someone new to programming (sorry to make an experiment of you !).
As for practical messy stuff, then look into Java (for basic static strong typing and endless tools), Perl if you must.
Another angle: Haskell seems to be popular for functional programming (as it is pure) - many people think functional's time has come, and there are some useful videos introducing it here: http://sequence.complete.org/hwn/20070807
Stick to things where you can get all the tools you need for free on the platform you use (and they are easy to get running).