For a gaming rig, the CPU is not your main concern. The GPU should be the most important thing on your mind right now. I suggest a motherboard you could easily upgrade with. PCIe 2.0 cards are still mighty expensive, so I would stick with PCIe X16 as their bus speeds are at least 30% faster than AGP 8X. But if your budget only allows for an AGP, don't count them out yet. There are still companies (Nvidia included) who are still making killer gfx cards for AGP.
Next, what operating system will you be using? If you are going to use Vista, you will Need a PCIe card with DX 10. You can still run DX 9 games, so don't worry that you will leave your favorites behind.
Next is memory. Keep in mind that the FSB tolerances for memory vary widely even in motherboards of comparable prices. AMD and Intel boards seem to need different types of memory for similar speed processors, so do your homework. I would suggest either Corsair, Kingston (with a life time warranty) or OCZ. They are slightly more expensive than their competition, but are worth every penny when squeezing every ounce of performance out of your rig.
And make sure your case has good air flow. If this is an mATX case or MiniATX, I would suggest big powerful fans at the front and back; one to pull air in and another to push it out. Some heat spreaders for your memory couldn't hurt and think about getting a PCI slot cooler to suck all the heat off of the video card. You could even replace the stock cooler on the GPU with one quite a bit better. Just be sure that the cooler will fit the cards layout.
The hardest part about building a computer IMHO is planning everything out and timing your purchases so that you take advantage of sales and rebates. After that you just hook everything up, install the software (MB drivers first, then upgrade them) and your off.
Send a post with your final specs.