I am for the most part self-taught so I hope my experiences would somewhat mirror that of yours. I started off with Pascal which was a very good learning language for me, but not very useful in today's environment.
You should start with a platform that interests you and pick a language from there. If you are interested in the web, then it probably wouldn't make much sense to make C++ your first foray into the programming world. If games are your thing, then C or C++ is definitely a good place to start. In short pick something that falls in line with your interests.
Once you have a suitable platform, identify a real world problem, something that bugs you or you think could be done better. Write an application that will solve your problem. I used to play a lot of Doom and Doom II and the gameplay became repetitive for me after a while. I wanted new experiences so I started to get in writing mods for games. That was my real world "problem" at the time. When I first got in to programming, my mother was working on her PhD, and she was having problems organizing all of her research sources, and didn't want to keep doing it on paper. I wrote her a small application that assisted her in organizing all of her sources, and she could also use it to scan her Word Perfect document for sources that were no longer being referenced. It would then alert her to sources in her list that no longer had references in her paper. It probably sucked, but I am her son, so she pretended to like it.
From there I just kind of naturally progressed. I found there were problems I couldn't solve in Pascal so I moved on to C\C++. I was asked to write some data mining scripts and found Perl to be suitable so I picked up Perl. I then discovered how Perl could be used to write CGIs and started getting in to web development, which then blossomed my interest to HTML, PHP, ASP, etc. I started working for companies who were more focused on Win32 development so I got in to Visual C++, and then to the .NET Framework. You'll find that you try other languages because you are always looking for ways to do things better.
Theory, design, etc. will all come later. Just jump in, get your feet wet, and start swimming. You'll make a lot of mistakes, and maybe even end up on WTF, but that is how we learn. I still make mistakes, and I still learn from them. Good luck!