Just my two cents:
Figure out what you want to do with the programming language first. Each language has its own strengths and weaknesses.
For just playing around in, definitely try Java. Java is about as easy as it gets to set up (no need to learn about compilers, etc. yet). Python may be even easier, but as some have mentioned it can lead to bad practices if its your first language. I love Python and use it regularly but I would never try to teach someone programming with it.
Do all the exercises Sqrl mentioned first. When you complete those, buy yourself a Data Structures book. DS are all the various ways that programmers represent information: lists, arrays, trees, graphs, etc.. 90% of the design work I do is choosing the right data structure for a particular problem.
A final bit of advice: start small and move up slowly. It's not sexy to be programming little Hello World type programs, but I promise you it is important.







