A format will almost always make a difference in performance, especially if you've acquired some spyware and viruses. Windows XP and Vista are pretty straight foreward to format, you pop in your Windows CD, re-boot, do whatever juju it takes to boot from the CD (most of the time this requires only hitting a key when it asks you too, some PCs you need to hit a button to get the boot selection screen first)
Then you setup your partitions when asked, I usually just delete the partitions there and re-allocate. In days long ago it was recommended that you split your partitions up into multiple sections to handle the sectors more efficiently but not really necessary, I like to put my swap in its own partition but that's preference. When you re-create your partition you will have to re-format, windows will ask if you want a quick format or standard. Quick just kills the table that tells Windows where the files are, standard will actually over-write all the data as well. Standard isn't REALLY necessary but if you have the time, I'd do it.
Once windows is installed, apply all your hotfixes from windows update, download firefox, AVG Free Edition or Avast, delete all shortcuts to IE and never* again have to deal with viruses or spyware.
*Not a guarantee but I did this with my mom's computer and it's been two years since I've had to service it.