Introduction to Computing and Programming in Python, A Multimedia Approach by Guzdial, Mark J., Ericson, Barbara [Prentice Hall, 2009] (Paperback) 2nd Edition [Paperback]
Solid book, got through pretty much every chapter. But the book wasn't as interactive as I would have preferred. It gave a lot of media examples and decent explanations but wasn't very interested in the sort of "think about it this way," or "as you are trying this on your virtual machine, you would expect..." which might have been preferred for my learning style.
It's trying but it's a kind of out-dated textbook since it deals with Python 2 and we're in Python 3 by now. I honestly don't think it's particularly useful to learn programming from a book, and mostly when I wanted to look things up I looked them up on stack overflow anyway.