After a week of dead ends and annoyances (NetRestore and SuperDuper don't like Leopard, BootCamp is useless, Windows stinks, Mac OS doesn't have NTFS RW) I now have the new iMacs and a general plan for building them as dual or triple boot machines.
1) Don't use BootCamp. I couldn't get it to partition things the way I wanted. I created a separate build on an external drive, booted from that and partitioned the internal drive into 4 logical partitions. 3 for the OSes, one for data. This left me with an OS-less machine.
2) Rebooted with my shiny new WünderWindows install disk and installed Windows in its own partition.
3) Rebooted with external drive and used CCC to build an internal copy of OS X. Dual-boot works!
4) Rebooted with Ubuntu install disk. Installed Gutsy. Note: install grub to /dev/partition-ID-of-install or there will be problems (with Windows, of course). I did a manual partition of the intended space in order to provide a swap partition. The original space was 32GB so I resized it to 30GB and set aside 2GB for a swap. Not sure if this is ideal, but it seems to work alright.
5) Installed Bootpicker, made some pretty pictures to represent OSes and voila! Triple-boot works!
6) Used WinClone to image the Windows partition, and CCC to image the OS X partition. No clever solution for the Linux side, although I did boot in to BartPE and ran ghost32 to create a .gho image of the Ubuntu partition. Haven't tested it to see if it works though.

Problems:
* xorg is a hassle. The graphics card is a Radeon HD 2600 Pro and isn't supported by the fglrx driver in the repos yet. I installed the latest ATI driver (8.42) from the AMD website (as in "not a deb") which installs, but gives crap performance - I can't seems to get HW acceleration and Xorg.log reports that the kernel doesn't support it.
* Wireless is a problem so far. Lots of reports on ndiswrapper working on it, so I'll need to do some more reading. Wired NIC works fine, though, so there's no hurry.
* iSight seems to work perfectly with v4l2 drivers.
* Bluetooth registers, but I haven't tried using it yet.

Next: get scripts working for deployment.
1) Auto-identification (as in getting the machine to automatically provide the correct hostname. Marc apparently has something that does this)
2) Bind to OU (again, Marc has this)
3) Test the Windows build in the lab. Get audio working and all the Sanako config files tweaked for USB headsets and the internal RealTek HD audio card.
4) Build the dual-proc G4 with Tiger server and see if I can get a NetBoot system working

Update: I downloaded Envy which installs the latest drivers from NVIDIA and ATI. It installed the 8.443 driver (I think that's the version) and now the basic setup works. Still no Compiz, but X is not laborious and unusable anymore. Still no joy on the wireless front, though.