Thats an AGP slot, a PCI-E slot has the keyed notch farther forward. Either a 3870 or a 4670 would be the best choice, toms did a review and found that many older systems couldnt make full use of the 3870 unless they were OC'ed.
A graphics card will increase performance, but what are his other system specs? If he is running a 3ghz P4, he will still struggle to play modern games. I am all for squeezing the most out a system, but sometimes these efforts become futile, especially considering AGP card prices now are inflated because of last chance upgraders desperate for a modern card.
The HD3850 is usually the best performer, having big fast local memory helps avoid swaps across the slow AGP connection, although there are some benefits to the HD4650 and it does use less power, better HD video and audio support, and on a low end CPU probably won't see much difference in gaming. The HD4670 (not reviewed) is sort of a balance between the two and likely your best choice for balance.
The HD3850 is usually the best performer, having big fast local memory helps avoid swaps across the slow AGP connection, although there are some benefits to the HD4650 and it does use less power . . .
That's a good point. When I wanted to upgrade my old AGP system a few years ago, I realized I needed a bigger power supply. A lot of the retail computers in the AGP days didn't have the beefiest power supplies (mine was a 300 watt.) Double-check that with with both the 3850 and the 4650.