Javascript and webdev is also a decent option since you can build such interesting and shareable web apps quickly, but the frameworks and scaffolding can be intimidating and painful.
I would work backwards from a project/interest and pick a high-level language where it's easy to get a good enough solution and create something that feels like an accomplishment. I would want to teach both programming as well as the joy of programming.