Well the vid card is important, but a move to the P3 1 ghz will make a tremendous difference for you, not only are you getting a 550mhz increase in processor speed but your going from 100-133 on your bus.It will deffinetly run any game out there nicely. Get a Radeon 8500 and you'll really be hummin.
Depends on your card. If your running at least a TNT2 (full version, not M64/Vanta), you'de get roughly equal results from either upgrading your CPU or your card. If your running a worse card (such as the MX200, Rage 128, G400), upgrade the card first. If your running a better card (original MX, MX400, GTS/Pro/Ultra, GF2Ti, GF3), upgrade the CPU first.