The textbook for AOPS "Intro to Programming" course "Python for the Absolute Beginner" by Michael Dawson seems to be good. (When deciding on the first programming language/textbook I looked at AOPS, udacity, etc., and liked this the most.) DC has gone through the whole book in the last few months completely on his own (with no previous programming experience) - I just installed Python on the computer. (Taking the AOPS Python course itself in the first place might have been better, but I did not know then whether DC would keep the interest for so long - it happened that he did.)

Another interesting resource (not to replace a language course per se) is USA Computing Olympiad online training pages http://www.usaco.org/index.php?page=training .

Quote
The USACO on-line training pages provide hundreds of hours of free instruction and practice problems to improve your programming and problem-solving skills.

These do require knowledge of Java, C++, or Perl (?) (Python is not currently supported).