Learn to Program, by Chris Pine, is a small, swift introduction to programming for beginners. Despite its short size (150) pages, and conversational tone, LtP covers a lot of ground, including:
The ordering of topics above is not merely useful pedagogically; it stakes out a position about what is important in software development. Note that recursion comes before OO, that OO is important but has no special pride of place over several other concepts, and that higher-order functions appear in an introductory book. None of this has been conventional wisdom in the past decade, but I'd bet all of it will be conventional wisdom in the next.
Of course there are a few nits to pick. The pace of the book revs up substantially (and suddenly) in Chapter 9. By then, hopefully the reader is hooked and willing to work a little harder. The book has a very personal style, with lots of first-person humor. Such thing are always a matter of taste; while I usually want my tech content straight I have to admit I chuckled a few times. Finally, I'd like to see a chapter on automated testing in all introductory texts; maybe that can get into a second edition.
Last Word:Learn to Program is a solid, cleanly-written introduction to programming for technical people. As a followup to this book, of if you are already a professional programmer, check out the Pickaxe, which is the definitive word on Ruby.