Heh, I used to have a 64MB Radeon 7000... It was a good card, played Civ IV with it (barely) for a little while, and it supposedly isn't supposed to be able to run the game at all.
I got a 256MB Radeon 9600 (AGP 8x) on sale at a local computer store for around $125 early this year (it happened to come with a free copy of Counterstrike: Source, too), and it plays GalCiv II and Civ IV perfectly fine, on maximum settings and 1280x1024 resolution. In fact, the only time I've really taxed it doing something would be when I went into flying camera mode in Civ IV and took this screenshot:
Link
You might be able to find yourself a good deal on a card over at www.Tiger Direct.com, also.