"Thus, teaching the non-interested -- or perhaps piquing the interest of the non-initiated -- can indeed be a formidable task."
Indeed. I've given up on trying to get my little sister (in 11th grade) interested enough to try programming, even though she did run Linux (exclusively!) for a couple years.
I always thought a decent idea to get someone started on programming from the ground up would be a simple, text-oriented RPG. This, of course, will work best if the person actually likes RPGs. This would be a simple introduction to basic ideas of control flow, data structures, and the like, but should be fairly fun.
I'd be willing to bet that you can actually write a decent game, with good combat mechanics and plotline, without having to worry about complicated user interface/graphics issues.
Another similar idea would be to start "programming" through some sort of scripting/creation utilities available in other computer games. MUDs come to mind as the obvious text-based choice, but games like Neverwinter Nights and Warcraft come with nice graphical level editors that have some scripting capabilities built in.