I'm going to go out on a limb here and say that it really doesn't matter which language you chose, and that the fact that you find python less surprising is most likely because that's the language you know best out of the two?
KidsHaskell FTW!
Trying to teach them KidsHaskell after they've become comfortable with KidsRuby on the other hand would probably be a bit more difficult.