How much are you willing to spend on this?
Here are some mobo's with both PCI-E and AGP. I would go with the first one (ASRock) if it was up to me.
For the CPU, I'd recommend, depending on how much you are willing to spend (cheapest -> expensive): AMD 64 3200+, AMD 64 3700+, AMD X2 3800+
Don't be fooled by the clock speeds. Even though they are lower than the intels, they perform better, especially at gaming. The number after the AMD 64 (eg. 3200, 3700) tells what speed pentium it is "equivalent" in performance to. The 3200 AMD = 3.2GHz P4, 3700 AMD = 3.7GHz P4, etc.
has some good info about the benefits of AMD and Intel CPU's. The current dual core AMD CPU (X2 3800 outperforms pretty much every one of the Intel Pentium D's (I don't know how it stacks up to the newest ones).