The more RAM and faster your computer is, the faster Virtual PC will run. I think you'd see the best performance from a late-model, fast G4 rather than a G5, since there are extra emulation steps that have to be taken on a G5 (little-endian vs. big-endian).
The older the Windows version, the faster it will run. Windows 95 will run faster than Windows 98 which will run faster than Windows Me which will run faster than Windows 2000 which will run faster than Windows XP.
Also, if you choose to run Windows 2000 or Windows XP, turning off "eye candy" such as fading menus and the candy-like appearance of XP will also help.
You can fiddle with the Windows settings to squeeze performance out of it, but ultimately, the raw horsepower of the computer is the ultimate determining factor. I've got VPC 7 running on my G4 in my sig, and it's bearable, but not speedy by any means. It takes a few minutes to boot up, and runs like I have it installed on an old 200MHz Pentium, but I get what I need to get done in it just fine -- albeit slowly.