My 3 year old daughter has her own portable (PIII with 64MB of RAM) running Debian Lenny.
I installed GCompris on there straight from the repos and she loves it.
She boots up and just waits for the desktop to appear (auto log in) and then just presses the flag key, I don't want her to get accustomed to the name "Windows"

, and the M key. Her name is Margot, so she recognizes the first letter of her name easily. A little shell script makes sure she can only run one instance at the same time.
She loves the GCompris environment. Every time she plays I see her progress to more and more difficult games. Her eye-hand coordination has progressed a lot since she first played.
GCompris is very much recommended.