i'd shoot for a 7800GS or 7950GT/X1950. i'm using a Radeon X1950 Pro in my shop computer and it can actually run some newer stuff on modest settings. like divide pointed out the cpu will either make or break the upgrade, so make sure the processor is up to the task of keeping up with graphics horsepower or the improvements will be lackluster.
check ebay for AGP stuff...