So my 3 year old is totally into video games (in particular a game on the wii called Excite Truck).
This game and a bunch of games on the iphone that he likes has led me to one conclusion.
Menus suck (especially if you can't read).
What would be best is a big Go button that is green and flashing. You press it, and whatever level, weapon, ship, car, gravity level, or whatever is just randomized. Finish your mission or die and you get another go button.
Below the go button can be Campaign mode, Custom, Settings, etc. I like tweaking out things and fiddling too, but always give the option of Go.