Yes, correct. You'd need Leopard to run Parallels Desktop 4.0 for Mac, then a valid CD for either version of Windows. Which Windows? There I cannot help you. 'Tis a choice you alone must make, young grasshopper, though the jman is right in that XP tends to use less system resources.
Desktop 4.0 for Mac also has different screen modes which can make it worth the trouble, depending on your setup. I personally like running OS X on one monitor, Windows on the other. It helps me keep certain things seperate and if I need I can still drag windows or files from one to the other.
When on a single screen, though, I switch to Coherence so I can just run Win & Mac programs side by side on my OS X desktop.
Kaspersky Internet security is also bundled with Parallels Desktop 4.0 for Mac as well as Acronis backup software; so there's a bonus if you're worried about the security of your guest OS. There's a trial available at
http://www.Parallels.com/desktop if you want to test it out after you get Leopard. You get the full functionality with the trial, there's just a time limit on the provided serial key.
Hope that helps some.