I think windows is probably safest. At least there is a lot of commercial experience out there if they run into difficulties. But probably the most expensive as a decent-ish box with a copy of SBS 2003 is going to hit the region of £1000, with a small UPS, disk mirroring etc.
As suggested, a cheap NAS is a good solution, and some do have functionality to backup to an external HDD (such as the buffalo terastation).
Another option is the Lacie nas which is Windows XP based and dead cheap. Doesn't offer printer sharing, but is so simple to administer and configure.
Finally, use one of the PCs to run a scheduled backup to an external HDD.
Simple and dead cheap.