My first instinct is to install Windows first, due to boot loader issues, but Linux has an issue where its boot partition needs to be within the first 1024 tracks on the disk, so it may make sense to install Linux first, so you can get that early partition.

Hmm, I think I'd probably install Linux first, making sure to install your boot loader on a partition, not the MBR, and leaving enough space free for a Windows install. Then install Windows in the free space, which will steal the boot partition from your Linux installation. Then boot back into Linux with your install CD, run fdisk and mark the Linux partition as the boot partition. Then you'll have to modify your boot loader to recognize the Windows install.

None of it is very trivial. It would be if Windows gave you utilities to really do what you want during installation and/or didn't try to take over your computer.