Going to try Python for Fun this month (http://openbookproject.net/py4fun/index.html) to get a bit more advanced and pick up Learning Python (http://www.amazon.com/Learning-Python-Powerful-Object-Orient...), unless anyone else has any other better suggestions?
Rinse repeat. You'll find that once you have one language down, the process will go much faster with the second. The features and syntax of most languages are pretty similar.
You can pick any language you like to start with, but personally I'd recommend starting with a hard typed compiled language rather than a dynamic language. Dynamic languages are easy to learn, but its easy to be a lazy and bad programmer in them. They let you get away with too much. Hard typed compiled languages are a) much better at catching your errors and b) much harder to be a lazy programmer in. They don't let you get away with things nearly as much.
I'd recommend Java, seems to be the language a lot of people start with. It will also give you a good founding in open source programming. I started with C/C++ and I'm glad I did. But that was more of a challenge - had to learn pointers and memory management in my first language. And after that I took a little while to learn the open source mindset, since I'd started in a procedural language.
Once you have a good grasp of an object oriented language like Java (or Python) and what object oriented programming means, then I'd recommend reading the Gang of Four book on Design Patterns (http://www.amazon.com/Design-Patterns-Elements-Reusable-Obje...) and Martin Fowler's book on Refactoring (http://www.amazon.com/Refactoring-Improving-Design-Existing-...). Those will give you a pretty good basis in software design and maintenance.
In terms of recommended reading for learning a language, the O'Reilly books are nearly always good in my experience. Here's one for Java (Learning Java: http://www.amazon.com/Learning-Java-Patrick-Niemeyer/dp/0596...) and here's one for Python (Learning Python: http://www.amazon.com/Learning-Python-Powerful-Object-Orient...)