Since I've been teaching myself, and especially since I've been flirting with several different sources rather than settling into a steady relationship with any particular one, I thought I'd share my impressions.
So you know where I'm coming from: I took AP Computer Science AB (Java) in junior year of high school. Then in senior year we had a semi-experimental Scheme class based on the classic SICP (see below), but nowhere near as hardcore. Because Java and Scheme are so different, and because I forgot a lot of Java over the intervening summer, this amounted to me learning to program two separate times with very little cross-contamination.
After that, I didn't write so much as a line of code for my whole first year at MIT. (Yeah, I know -- how could I?!?, etc.) But somehow a lot of vague programming ideas seem to have stuck in my brain, making it much easier to (1) learn a new language, and (2) re-learn programming in general. So I'm somewhere between 'rank beginner' and 'person who wants to pick up a second language after their first CS class'. This will affect my assessment of resources.
>> Learning Python, Mark Lutz & David Ascher
...Comprehensive, I suppose. It's the O'Reilly book, which gives it lots of reputation points. It goes into a lot of detail about basically everything (I'm reading it online, but the dead-tree edition is quite hefty). Tables of built-in integer and string functions, that sort of thing. Even -- get this -- more than one chapter on getting Python to run on your system, choice of IDE, and how to run programs you write from a variety of situations. This makes it surprisingly useful as a reference, for a book with the word "Learning" in its title.
The thing that bothers me about this book is that it can't seem to decide where it's aiming. It's definitely a programming book, not a computer science book; but it's in between "dense comprehensive tutorial/reference for people who already know what they're doing" and "learn programming from scratch using Python". For example, it explains the ideas of iteration and recursion, gives very basic examples, and discusses the general sort of situation in which you might want to use them -- and then a minute later it hits you with a lot of jargon and dense stuff. Curious approach.
Perhaps some of the confusion is because the authors are trying to take a "quick survey first, then dig into the details" approach on each section, and their definition of "section" is too short, leading to a confusing rapid alternation between the high view and the details.
I'm only up to the section on classes and OOP so far, because I've started to run into stuff I never learned or have forgotten; so I can't comment on the GUI section or anything like that, but I'm sure everything else is quite comprehensive.
>> Structure and Interpretation of Computer Programs, Abelson & Sussman
Ahh, the classics. Especially the classics that are available online, for free, in full, under Creative Commons, and not in a really irritating interface!
This is a hardcore nerdy book. It doesn't teach you computer science, it ties you down and throws computer science at you thick and fast, but in a totally awesome, non-evil way. It's really not a programming book, either -- the authors go out of their way to teach you the absolute bare minimum of Scheme syntax to handle the concepts they're presenting. This is kind of irritating if your goal is to be able to do practical things quickly (ha). But if your goal is to achieve nirvana, you could do a lot worse than this book.
Read the footnotes. They are snarky, and competently so, unlike the lame attempts at humor you see in most textbooks.
>> Teach Yourself Scheme in Fixnum Days, Dorai Sitaram
This is a straight-up no-frills tutorial for people who already know how to program, more or less. Reading this after having taken a SICP class was pretty interesting: I kept going "Hey! That piece of syntax makes it really easy to do X thing we were always beating our heads over in class, because SICP HATES SYNTAX OR SOMETHING." Hooray for actually doing things with Scheme. I'd gotten the (not entirely wrong) impression that Scheme was good for nothing but theoretical interest and formalism with a dash of AI.
I'm not sure whether to recommend reading this along with SICP. On the one hand, I tried it and got really confused. Part of the charm of SICP's syntax starvation is that it actually helps you figure out how to do things; they simply refrain from teaching you the four other ways to do it. On the other hand, Scheme can actually do stuff that's not all abstract and theoretical and weird, and this teaches you how to do that.
>> [pdf] How To Think Like A Computer Scientist: Learning with Python, Downey, Elkner, and Myers.
This, I think, would be a good book for a (dedicated) beginner. It starts right at the beginning with the very fundamentals, and keeps a great balance between new concepts and new syntax. I haven't gotten very far at all in this book, mostly because I've spent so much time on the O'Reilly Learning Python book, but I like it very much so far.
Plus, how can you say no to a book that's written in LaTeX? Seriously, now.
>> Project Euler
Oddly enough, none of the above books have enough exercises in them. Teach Yourself Scheme has none at all. Learning Python only has a few, once every five chapters or so, and they're all about catching tiny nitpicks that trip you up. SICP has plenty but they're geared toward teaching CS principles, not coding practice. How To Think Like A Computer Scientist has good ones but not many of them. I googled around but the only thing I found that wasn't too advanced was FizzBuzz, which wasn't enough.
Enter Project Euler. It's a site full of math puzzles, varying in difficulty from "ludicrously easy" to "frackin' impossible", and set up such that you basically have to solve them by programming. Things like "find the ten-thousandth prime number", too big to be solved by hand. Excellent!
The site is obviously run by people who know what they're doing -- all the problems are very unambiguously stated, with examples, and the site keeps your score for you. Once you've solved a problem, you can look at the discussion thread where other people post their code and discuss alternative methods. The other people, by the way, are brilliant, and come up with all these elegant methods and neat optimizations for you to imitate.