Reformat

What makes you think that you m/c isnt infected with any virus. Did you scan your m/c with the latest definitions of your Antivirus software? If not, pls do it first.
Then uninstall any unwanted programs which you might have installed sometime back. Next try to defragment all your drives and try to recover some disk space. Also make sure that on your primary partition where the OS is installed, you have enough free space. Also delete all files in your temporary folder and clean up the 'Temporary Internet files' folder.
After all these, check your m/c performance. If you still find it to be slow, then backup all your data, reformat **only** your primary partition (C: in most cases) and reinstall the OS. If that too doesnt help, then do aclean/fresh install.

If possible backup all programs and apps you want to keep
Insert Windows 98n startup disk in floppy drive and boot computer,then choose to run setup without cd-rom support,at the command prompt type FDISK
follow the onscreen instruction to delete primary partition,continue to follow the onscreen instructions

First of all, there's no reason to fdisk your drive. That's just an extra step and formating it alone will be fine.

Secondly, if you're running Windows ME get rid of it. Biggest piece a crap MS ever put out.

If you're running win2k/XP the cd should be bootable and it will let you format from the setup

If you're running win98 or win95 use a windows boot disk to boot from with cdrom support. Type "format c:" w/o quotes when the boot disk is done booting.

You'll then want to copy thewin98 (win95) folder to the hard drive and install the OS from the hard drive. Do that by typing at the command prompt:

c:
md win98
cd d: (or whatever your cdrom drive is now)
cd win98
copy *.* c:\win98

You should then see a bunch of files start flying by the screen. It's copying all the setup files to your hard drive. This way, if you ever install drivers or new components you don't need the win98 cd, it will copy the files it needs from the hard drive.

when that's done switch to the directory you just created and type setup:

cd c:
cd win98
setup

you should be all good after that

You can try just reinstalling Windows for a quick fix, but I wouldn't do this more than once!
Insert your Windows CD browse to setup, click on setup icon and follow instructions. This will copy any missing or damaged files, and should give you a definate increase in performance! If not your looking at a clean format and install of EVERYTHING !!!