This is if he also wants to change his processor as he won't find PCI-e mobos for a socket A CPU. There are very fine AGP cards too.
ATI will also release the X1600XT in AGP soon:
http://www.theinquirer.net/?article=28159) which seems to be a very good choice for a middle range GPU.
If he changes his processor, PCI-e is the way to go in order to have a machine that will be more easily upgradable in the future and there's no point in buying a new mobo that supports only AGP at this time. However, in terms of immediate performances there aren't noticeable differences between the AGP version of a card and the PCI-e version.