I think I would approach that with a game or something very visual (see Processing?), and work with them in defining what things they want to see happen in term

I think I would approach that with a game or something very visual (see Processing?), and work with them in defining what things they want to see happen in terms of instructions or pseudo-code. For example, you could start with the idea of a game like a simplified OutRun and brainstorm about what should happen. Well, you want to be able to change lanes, right? You would want to have cars coming your way, the speed increases as you go, etc. so that you end up with a list of things to happen that can be translated into code that does what they wanted to do. I'm not sure this is a great example, but in principle, it would be to make them walk through the idea of defining what should happen in a program. To me, I don't think that the language matters, I don't even think that they really have to interact with the language at all or a very simple and specific language. What's important is to understand the process of: this happens ("I press the left arrow") so that happens ("the car moves to the left"), from which you can introduce conditions, loops and more. As a starting point, you could also ask them about what software they use often and see if you can build something very simple around the same core concept.