Yesterday I did something in Parallels that I'm embarrassed to say I hadn't done before--it made a huge difference. I installed the Parallels tools in some guest OS's and compressed and defragmented their disks.
The guest OS tools allow the guest OS to play better with the host. The biggest difference you'll notice is that the mouse "rolls" from the guest to the host OS without the need to push funny key combinations to "release the mouse." Not only that, drag and drop and cut and past work. Hurrah!
Compressing my disk images cut them in half (6Gb to 3Gb) and while I didn't do any scientific study of their performance they seem zippier. Warning: compressing takes a long time, but it's automatic. Turn it on before you go to bed. And be sure to install tools and compress images before you clone them.
The bad news is that while this works fine in Windows XP, there are no tools for Fedora (I don't know about Redhat) and I don't believe the compressor works on Linux distros. As long as we're on the subject, Fusion has a set of guest OS tools as well and those are available for Fedora in addition to Windows.
The lesson: a little tuning of your virtual image, done automatically, can dramatically affect your experience.