I have both socket a, socket 754 and socket 939 builds. In fact my current main retro-rig is a socket 939 build: Win98 Socket 939 Voodoo 2 SLi Build! (a.k.a. Glide Overkill)
There are several advantages to a socket 939 or 754 build. The are a bit cheaper and easier to find, and the're also cooler and more stable then their socket A counterparts. All socket 754/939 mainboards also have win98 drivers except for the nForce 4 witch is out of the question since you want to use an AGP card and that only comes with PCI-E. I personally use a VIA K8T800 PRO board for may voodoo 2 sli build and it's very win98 friendly (just don't try to install USB 2.0 drivers). Speed-wise an Athlon64 is a little faster then an Athlon XP at the same frequency (10-15%), and the A64 is way cooler and goes up to 2800MHz on socket 939 (Athlon FX-57). The fastest non-FX socket 939 CPUs top out at 2.4GHz and are the 3800+ venice (512kb L2) and 4000+ san diego (1mb L2).
Some 754 CPUs are very overclockable. I have a socket 754 A64 3000+ venice that effortlessly goes to 2333MHz w/o touching the voltage (233MHz x10). My 939 3800+ will go as high as 2796Mhz but requires additional voltage and proper cooling. Just remember to lower the HyperTransport and Memory clock multipliers when overclocking. I use 233FSB, set the memory to 166 in bios resulting in 199MHz memory clock and the HT multiplier to 4x resulting in 933Mhz HT clock.
Voodoo cards will also work great on it - they are not bothered about the 200Mhz fsb. They only start acting up when going over 233MHz, and not on all boards.
I also do not recommend using modern graphics cards on a machine built for old games. Some games don't like newer graphics cards. I've found that if you use anything faster then a Geforce 7900 or a radeon x1950xtx some games refuse to work (Dungeon Keeper II - black screen issue) or will not run correctly (Black and White 1 - texture corruption). 2D games like Red Alert 95 and StarCraft witch rely on older versions of Direct Draw will display color corruption on some newer cards - there are patches to fix this tough (at least for Red Alert).
I'd say, depending on what you want to play, a socket 754 Athlon 64 3000+ and a geforce 4 titanium should be perfect for games up to 2003-2004. I've played Black and White 1 FULL HD (1920x1080) on one such setup. Or you can go for a 3700+ and a Radeon 9800 PRO or a 6600 AGP. The fastest card witch will not be slowed down by the CPU is probably a 6800XT or a X850XT but these are pretty hard to find and getting more expensive by the day. Any faster and you'll need to upgrade the CPU again (Doom III, Quake 4 like really fast CPUs, lots of VRAM and are multi-core aware).