$500 can get you plenty because you don't need but a basic 2d video card
I haven't run a game server myself, however I can guess what would be good. Your two most important components will be RAM and processor speed, so get as much as you can of both. In other words... Price out a cheap motherboard with lots of integrated stuff (such as the Asus A7N226). This has integrated graphics and LAN. Next, look for a case and a CD drive. If you're going big on the cheapness, you can get both for $50.
The rest can go to RAM and processor.
So here's what we have:
Asus A7N266 - $68
Case and CD Drive - $50
-------------------------------
$118
That leaves us with $382
That's a lot of dough.
512MB PC2700 from Crucial will run $82
Now we're up to $200, leaving $300 for whatever else.
What I would do is grab an Athlon 2000 for $71.
This will bump your total to $371, which is $129 under budget. Nice Job!
Go buy yourself a damn copy of Battlefield 1942 with the remaining money and play a game produced in this damn millenium.