Setting up a PC for the Kids
Solution 1:
I've recently switched to use OpenDNS for blocking/filtering duties. There's a free account option that works spectactular. Even better, they recently introduced FamilyShield which is a no configuration/registration option. Standard filters are preconfigured and you just point your DNS to the FamilyShield IPs.
What's great about this is there's no easy way to circumvent it since its not a program that's running in the background to try and disrupt. I would make the category filtering in your OpenDNS account settings as strict as possible for your children.
At their age it's probably making sure an accidental click doesn't take them somewhere it shouldn't; as they get older it will make sure their curiosity doesn't take them somewhere they shouldn't go.
Also, you could and probably would set the kid's PC to use those DNS servers and leave yours as is. Then you would rely on proper user permissions (non admin/root) on child accounts to prevent tampering with DNS. (If you go this route there are some technical details with OpenDNS and making sure your local computer names route correctly, read their documentation.)
I'll add that there is no perfect combination of operating systems, software, internet filters, antivirus, etc. that will make up for a lack of involvement, care, and sensitivity with our children, we should all keep that in mind. However, being thorough and vigilant in this area cannot but help.
Solution 2:
I started my kids when they were around 4-5, and at that age it's all about the games - you can probably get away without internet access for a while, so they're safe with XP and no anti-virus. A regular keyboard and mouse were fine.
If you want to give them internet access (for the flash games) then you might want to consider a linux-based distro with firefox. You can do blocking by using openDNS.
Solution 3:
If you're taking the Linux road, you may want to consider Edubuntu.
I think blocking Internet entirely would be sensible. There's far more risk than reward at the ages you're talking about. Install some games and have big friendly links on the desktop; that's all they need until they show more curiosity.