Squeak eToys include a lot of nice goodies. You need to play around with them enough to be able to guide them through to get the most out of them, however. (This probably goes for anything mentioned as a suggestion, of course.)

If you want to make them really uber: From Nand to Tetris in 12 Steps!

http://www.youtube.com/watch?v=JtXvUoPx4Qs

All the courseware is open source.