The first thing I do when someone tells me that they want to learn how to program is teach them how finite state automata work. If they seem to enjoy that, walk them through the NFA to regular expression proofs. Then we have a talk about the data structures that would be involved in storing and manipulating automata, regular expressions, and their input. Finally, I recommend that they start playing with SICP or How to Design Programs. The people that I've introduced to programming this way have a fairly sophisticated, "no-magic" attitude earlier than is normal. Introducing automata first provides a really good way to talk about machine model (automata itself) and programming language (how to specify the automata).