I like OpenFeint too, but there are some things to keep in mind. First, integrating OpenFeint adds a few MB to your app size if you support both landscape and portrait modes (I'm not sure what the exact size is - sorry). This can be an important consideration if you're close to the over-the-air limit. Second, Free Game of the Day is a great program, but it is something you need to apply to. Not every game gets accepted.

As far as FGOTD: OpenFeint contacted us to use our game for FGOTD - we didn't really apply or anything like that. However, word of caution - any time your game is free, you will get bottom-feeders expecting everything (this is a different discussion altogether)

Back to the point, we only use our game in landscape mode, and we went from 70+ source files to 900+ source files after we added OF. So yeah, good point about OTA limit. :)

Alice and Scratch both look like good learning tools (and have educational research backing them up).

I think it's more important though that there's someone who loves hacking in the child's life. Children pick up on genuine enthusiasm quickly, whether it's from you, your spouse, or someone who's a role model.