I'm teaching a relatively mathematically-minded friend programming and I've found http://repl.it/languages/Scheme to be an excellent resource. The simple syntax and semantics of Scheme and its easy accessibility allows them to quickly develop an understanding of the fundamentals, and from there it's not much work for them to download DrRacket and start on more practical applications.

I think games are a great place to start; simple, humorous text-based adventures, for instance, are both really fun to write and teach a lot of the basics.