The first thing to realize is that you are a programmer. The biggest difference between someone who calls himself a programmer, and someone who does not is the attitude they have toward computer use. The definition of computer use that you apply will determine whether you become a victim of the technological designs of others, or become a competent user of technological tools.
The difference is attitude. I'm not saying that every person who turns on a computer is a potential Richard Stallman, but your goal should not be becoming the Last Real Hacker; instead your goal should simply be gaining technological competence and skill. You can do that. And the first step to believing you can do that is to change your mind and say "If I learn, I will know how." You don't know now, but you will know after you learn.
As evidence, take myself: I used to believe that learning to program would cost tons of money, and so I rejected learning to program as a tool of the establishment, something that people only did if they wanted a job with Microsoft. During all the time I believed that my friends and colleagues were gaining programming skill that I refused to get on my own. When I finally did take the sensible route and just look up what I needed to start programming in C, I discovered that free C compilers were readily available, and in fact whole operating systems had been built around them, along with free programming libraries and manuals.
Boy did I feel like a fool.
I found out that a whole culture exists, built around the ideal that being a computer user is far more than picking up a mouse or putting your hands on a keyboard. The community of Free Software is built around an older notion of what it meant to use a computer. In particular, it recognizes that whatever a computer is designed to do, or whatever programs you have available were not designed by you and therefore do not know everything that you want. If you accept that everything a computer does is something that you already want, you're limiting your desires based on what someone else tells you. You're subscribing to the idea that whatever someone wants to sell you is all that you should ever want. There is a very successful hardware and software company built around this notion, and people totally eat it up.
However, in the old days, you couldn't take what a designer gave you: computers didn't do anything "out-of-the-box" and you had to have the attitude that to use a computer is to modify its operations and give it specific instructions. With modern computers doing so much that is flashy and impressive, including eclipsing many other household electronic devices and consolidating entertainment around a single machine, computer consumers think that they don't need to extend what a computer does, or write their own programs.
They're wrong. Those same people, who think everything is sewn up when they turn on the computer, come to me saying "How can I make this happen? How can I perform this more efficiently? How can I replace this text with this other text, where I don't know completely what I want to replace?" The answer is to become a programmer.
C is often thought of as "advanced" and teachers encourage students to learn Java instead of C; I recommend learning C at the same time as learning Scheme, Common Lisp, Python, and Perl, since C is a different kind of language than all of those (as they are different from each other). When you program in C, you learn to directly manipulate the registers of the machine, something that will help all your other programming. The hardest thing about C is just bookkeeping (function prototypes, includes, macros, etc), rather than the programming itself (see Recommended Reading). Most languages themselves are implemented in C, and using C libraries with a foriegn function interface from your chosen language (e.g., Scheme or Python) is a great way to program.
Perl was a very popular language for web programming and CGI; it has found a second wind in bioinformatics. Two things you should know about Perl:
Another thing about Perl is that it has a whole culture of people who write code to do anything in Perl, even stuff it's totally inappropriate for. Perl is not as popular as Python now, but you'll still find plenty of books about it, and plenty of it out there on the web.
These last three there are forms of Lisp. Although they are quite different as dialects, they all have a little bit of the Magic of Lisp. The best part about Lisp is that it's addictive and convinces you that there is no other true language. Once you get bitten, it's hard to come back.
A couple of things that I noticed when I started learning to program were that
As for the first point I've noticed that most programming texts (except the really good ones or the ones specifically aimed at beginners) are for people recovering from programming in languages that they didn't choose, mostly C++ and Java. Most of the stuff I read about Python was directly framed in terms of stuff you'd only know if you'd spent years progrmaming in C++. The other thing is that I'm primarily interested in numerical analysis and text processing, so it's strange that most of the stuff I come across is about web programming. The web is now the biggest market for programming and for people who want jobs doing it, that makes the most sense. This demand also creates the biggest market for books. The books I recommend below are more well-balanced.