My children (I'm a proud Dad of 4 children) started using Macs at 3.
After trying to install an old Pc with Windows 95, and spend most of my time repairing it after they clicked twice or turned it off in the "wrong" way, I switched them to Mac.
I was given old Macs (Mac OS 8), all in one, with colour screen included and just left them near their playground. They started playing with th mouse, trying to hit the keyboard and finally got really surprised when it turned on !
Next, I installed very easy software for children (sorry, french : lapin malin maternelle 1, nounours...) which just show how to wipe the screen with the mouse or randomly hit the keyboard to produce sounds or figures.
Slowly, when they grew up, I explained how to clic and launch small games.
The mac can be turned off / on without any concern, and children can mess up the icons, everything still work !