I think the best introductory book to programming that I've ever seen is Learn to Program, by Chris Pine. My buddy I was staying with last summer went through it while I was there and made absolutely fantastic progress. Despite never having programmed before, really, he tore through it in a week or two and got enough out of it to start programming simple scripts to help with his research job.
The entire book is taught in Ruby, but I don't think the language used matters that much. The thing is it teaches concepts basic to almost any kind of programming -- functions, classes, recursion, blocks, etc... And more importantly, it makes them fun! Even the very simple exercises, such as "deaf Grandma" and "angry boss" were amusing. My friend has ended up working almost entirely with Python, but everything in the book was still useful and there was little pain in switching to a new language compared to the difficulty of getting started.
When I first got curious about Ruby myself three years ago, I tried the Pick-axe book and gave up out of boredom. It really could have used regular programming challenges or problems at throughout the book. Unfortunately almost all the other resources that were around at the time were focused on Rails. I really wish I'd found this book back then.
Some free online lessons that later became part of the book can be found here: http://pine.fm/LearnToProgram/