I've refurbished dozens of business computers for kindergartens, families and senior citizens that can't afford a computer.
Install the latest version of Ubuntu. If you absolutely have to run a Windows app that just won't work under Wine, use VirtualBox.
Don't let your preconception limit the children. I've seen competent use of Blender at 8, Impress at 6, and GIMP and OpenOffice at 4. Without any guidance from adults. It doesn't hurt to have an app available.
For preschoolers my set is:
sudo aptitude -y install wine unzip
sudo aptitude -y install kstars
sudo aptitude -y install gcompris kolourpaint kolourpaint4 kig ktouch kalzium ktuberling atomix kanagram khangman tuxmath xaos tuxtype parley-kde4
sudo aptitude -y install parley parley-kde4
sudo aptitude -y install dia-gnome
sudo aptitude -y install gpaint scribus kwordquiz marble step sudo aptitude -y install rhythmbox kino tuxpaint gimp gthumb inkscape totem
sudo aptitude -y install armagetronad epiphany lbreakout2 powermanga rafkill ri-li frozen-bubble gnome-games freeciv-client-sdl gnome-terminal pingus supertux-stable
If your video card supports them (it almost certainly will), consider some of these - I haven't evaluated them for suitability for K4, as the machines I get are much older and less powerful:
# sudo aptitude install stellarium flightgear chromium btanks extremetuxracer fretsonfire neverball nexuiz openarena planetpenguin-racer rrootage supertuxkart tremulous warsow xmoto smc torcs glest vegastrike warzone2100 scorched3d supertux
The above list hasn't been updated since March 2009, I'm mostly dealing with school age children. For them I use the following, althought this is also the set my 4 year old daughter has been completely comfortable exploring and using:
sudo apt-get -y install wine evolution unzip vlc ubuntu-restricted-extras gtk-recordmydesktop sudo
sudo apt-get -y install kturtle gcompris xmaxima kolourpaint4 kbruch kig ktouch kpercentage kmplot kalzium ktuberling atomix kanagram khangman tuxmath xaos tuxtype parley-kde4 xiphos
sudo apt-get -y install parley parley-kde4
sudo apt-get -y install dia-gnome
sudo apt-get -y install qcad gpaint scribus kwordquiz marble step
sudo apt-get -y install sofastatistics
sudo apt-get -y install kolourpaint
sudo apt-get -y install kstars
sudo apt-get -y install armagetronad atanks blobwars epiphany lbreakout2 powermanga rafkill ri-li uqm frozen-bubble gnome-games wesnoth freeciv-client-sdl gnome-terminal glob2 pingus beneath-a-steel-sky wormux supertux-stable
sudo apt-get -y install freecol sun-java6-bin
sudo apt-get -y install rhythmbox kino tuxpaint gimp gthumb inkscape totem blender pitivi openshot
And with a powerful enough graphic card:
sudo apt-get -y install stellarium flightgear chromium btanks extremetuxracer fretsonfire neverball nexuiz openarena
sudo apt-get -y install planetpenguin-racer vegastrike
sudo apt-get -y install rrootage supertuxkart tremulous warsow xmoto smc torcs glest warzone2100 scorched3d supertux
My full set fits in 20 Gb. I have a remove list when I need to fit into 10Gb drives. I welcome any additions to the list.
I found it surprisingly difficult to find a comprehensive list of games and educational softwatre for young people on Linux. I hope my list helps someone. This list is in addition to the software that comes with a standard desktop install of Ubuntu. I don't use Edubuntu. I thought their extra software choices were paltry and that anyone could do much better. I think I have.