Here is my progression:
I had the ti4200 AGP 8x. It is a great card. Served me well for about a year. I then wanted to play around with DX9 games (Doom3) and video recording/PVR, so I went with the AIW 9600XT. Not only did I get more functionality, but better performance. So I enjoyed that card. I must say though, I never was able to fully utilize the TV tuner. I was always getting poor reception, even with cable, but that's a whole other story. The bummer however was I was upgrading my display to LCD and needed DVI. The AIW 9600XT does not have a DVI connector, just 2 VGA connectors. That wouldn't do, so I wanted to upgrade again. Well it just so happened that the NVidia 6800 was on sale for a great price ($249), so I went with that. Whhhoooowww, what a difference. I mean, before I could run games at 800x600 with small lag, now I'm running games at 1280x1024 with absolutely no lag. It looks great on the LCD and it pratically doubled all my frame rates from 30's-40 to about 70's-80's in most of my games. To me, that was one of the best upgrades I could go with. In the back of my mind, I wished I would have gone the 6800 GT route w/ 256meg. But it works great and I won't feel like my stuff is going obsolete in 6 months to a year. I will go PCI E at some point, but AGP is just fine.
The bottom line, go with the best card you can. Shop around, set a price in your mind you are willing to pay and meet that goal. If you can only afford the 9600XT, go for it. If you can higher, do it. You'll be much more satisfied in the long run. Satisfaction is worth the extra few bucks.