Generally MS Windows likes to be installed first. When I'm setting up a dual boot (which honestly I haven't done in a while since I tend to just use a spare harddrive instead), I always install XP first, then Linux, and tweak the Linux bootloader to load XP. Some distributions will set up the XP boot option automatically for you.
The other is totally reformatting the whole HD and with either install parting the hard drive.. I think it would be easier to part with Linux but the question is with this option which OS should I install first?