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 to newcomers (in my opinion), people like to be "clever" in ruby, and then there is the hype (this is my personal opinion - although I find ruby much easier to use myself, and its OO approach suits me a bit more then python).

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 !). Someone tried to teach this stuff (kind of) to me once in miranda (didn't work to well as a first programming language).

As for practical messy stuff, then look into Java (for basic static strong typing and endless tools) and Perl if you must, the basics of C to wrap your head around pointers may help - I learned that around the same time as motorola assembler (much nicer then intel) and it helped form a mental model of 'on the metal' computation which I found helpful.

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).