yeah, 500 bucks for a gaming pc is pretty tight. But if you need to stick to that budget, I'd start by upgrading your video card and getting some more memory, and maybe upgrading your processor if you can. That would be a good start and see where you are after that.
What are the specs on the system you have now?