I think the question "Hey, I want to learn how to program! What do I start with?" is typically the wrong question to ask.
It's more important to be interested in making something; anything, that would impossible to create without programming ability, and then to thoroughly investigate that part of the programming world either in tandem with CS coursework, or to be aware that the "theory" of CS is out there, and that there are resources that exist for that.
I know you can go your entire programming career (professional or hobbyist) without being exposed to the "bits" as I like to call it (lower level programming, academic programming, theory) and be perfectly content with your knowledge so long as what you are trying to do is often "solved problem programming" -- that is, you aren't expected to do anything for which there are few resources available to help you with. Or none, for that matter.
I think you can become an accomplished web programmer, or "retro game coder", or software engineer by picking a book that gets you started on that topic, and letting the author's choice of language be your entry -- assuming the book doesn't take the approach that you've programmed before.
On the other hand, there are certain fields where not just anyone can reasonably be expected to go off and do things effectively without having a heavy list of per-requisites met, and this generally includes a lot of academic know-how (Data structures, algorithms, those kinds of things), a strong grasp on mathematics, and simply a lot of experience. These are the kinds of things where a very specific skill-set comes into play, and that's the kind of skill-set that one gets from a long period of study, exploration, and failing enough that they've learned how to succeed. The point of a CS degree, in my opinion, is to help programmers become aware of problem-solving techniques that have existed in theory since before you could write code to do it! These are things where you run into a problem and say "Ah! I've seen this before!" or "I've been here before" and you instinctively know the tool for the job, and the theory cements your rightness about the choice for the direction you take on solving that problem. Maybe you haven't seen the problem before, and you can take an amalgam of other things which form a "new" solution. All of this is a result of learning how to be a "thinking" programmer. a White-box programmer instead of a Black-box one. Heavy academics and training can help here.
So the question of "learning to program" is faulty by nature of the beast. Some people want to learn enough to get done a particular task, others are much more dedicated to the field itself and want to know the ins-and-outs. I've been programming for 8 years, and I never feel like I know enough, and I'm always catching mistakes that academics tried (and continue to try) to drill out of my head, and in my spare time I'm generally experimenting with mathematics, and games programming, and just constantly learning. I learn something new nearly every day, and it gets me thinking about things I couldn't do in the past that I may be able to do later.
The greatest singular piece of advice I could give to another learning programmer (and you should always be learning) is to, when you are ready, teach. Learning by teaching is one of the most powerful tools, I think, so if you have the option to TA, or something, do it. If you have a friend who wants to learn how to code, and you just started, "act as if" and help him learn. Get involved with other people who program, and share what you know, and learn from them. Try to forget about language rivalries, and other things that aren't at the core of the (loosely defined) science.
And obviously write code a lot. Don't ever turn down writing something because you think you can do it; write it, so that you know you can. The small skills and insights you develop from writing the simplest of things can stick with you forever.