Here's what I would recommend (most of this from Newegg):
Enermax black Mid-tower case w/ 350 w power supply: $55
Lite-on black DVD drive: $33
Maxtor 80 GB HDD: $77.50
Kingston PC2700 CAS 2.5 DDR RAM: $81
ABIT nForce2 SPP: $71
Athlon XP "Barton" 2500+: $80
Radeon 9500 Pro 128 MB VRAM: ~$100 - 125 on eBay
Total price: $497.50 (assuming you pay $100 for the vid card)
Rationale:
The case isn't something I have any experience with, but it fits the bill of being cheap yet attractive, and the reviewers on newegg really seemed to like it.
The DVD-ROM drive is still an easy choice. I've heard some things about Lite-on recently that worry me, but never in reference to their DVD drives. You can't get a better DVD drive period, and when you throw in that it's the cheapest, it's a no brainer.
The hard drive seemed to be priced in that sweet spot where you pay too much when you move up and lose too much when you move down. It's a Maxtor, of course. A man who never buys anything but Maxtor hard drives will be a happy man.
The Kingston RAM had a good combo of price, performance, and reputation, although I've never personally used them.
Processor is the best dollar for dollar deal in the industry and has been for quite some time. Move down the ladder and you're getting screwed on performance for minimal savings, move up and you're paying too much.
Motherboard was an easy choice. nForce2 with SPP has been known as the best Athlon XP board for a long time.
Video card was a bit tricky. At first I wanted to recommend the Sapphire 9800 pro at $215, which is a phenomenal deal, but that would have put you at least $100 over budget. The 9600 XT was better at $150 but still not great. The Ti4200 is a nice card and can be found for $50-70 on eBay, but I think the best deal right now is the 9500 pro. It's faster than the 9600 XT in most tests, and will stomp a Ti4200. This is because it's built on the same core as the 9700 rather than a "budget" (aka crappy) core like the 9600 series.
*Looks at clock, sees that it's past bedtime* Well, that took a little longer than I wanted it to, but I enjoy this stuff (can you tell?) Hope the new machine works out for you. Good luck!
EDIT: Btw, in case you were wondering, even though it's on a $500 budget, this is not a feeble computer by any stretch of the imagination. This thing would absolutely curbstomp my machine and most other people's as well. So don't feel like you're screwing yourself by only spending $500.
2nd EDIT (then I'm done
): And yes, it will run Half Life 2 and Doom 3.