My kid started playing with Lightbot[1]. It teaches recursion, loops, conditionals, and is fun. I would recommend LOGO as an elegant functional programming language, if you want something besides the usual ugly python for-loops; Berkeley logo for quick REPL, NetLogo for more advanced concepts as agents for example.

[1] https://www.youtube.com/watch?v=qZFK5yKQLdU&list=PLL6dgai5Nn...