Eu comecei a aprender Python há pouco tempo; posso dizer que é uma linguagem bem tranquila, e que tem MUITOS recursos na internet.
O melhor livro que eu vi pra um iniciante (em programação), foi o
How to think like a Computer Scientist - versão em Python. Ele não só ensina a linguagem, como mostra a um iniciante o que é programar. É muito bom.
Como o Darcamo já disse, tem o Dive Into Python que, apesar de ser voltado àqueles que já programam em outras linguagens, é bem tranquilho de acompanhar, e é uma ótima opção pra se aprofundar.
No Ubuntuforums.org tem um tópico com uma série de links muito úteis pra quem quer começar a programar, em qualquer linguagem. O post sobre Python está
aqui.