If you can wait and save up some money, Sapphire is releasing an HD3850 for the AGP bus. It will be the best card for AGP and will allow you to avoid having to upgrade your whole system for awhile longer. http://www.techpowerup.com/index.php?48796
No mention of price, but it should fall around the $200 mark.
Less memory isn't better if it is clocked the same. BUT, it is very often cheaper. And 512MB is typically going to help most at higher resolution and/or with FSAA or with massive textures (says Oblivion texture mod). And even the 2600XT isn't going to do very well in those cases. That is why he would recommend the 256MB card....save you money. If priced the same and clocked the same by all means go with the 512MB card. But if the 256MB is a fair amount cheaper or it is clocked higher( say GDDR3 in the X1650,s or 2600 pro), then grab the 256MB card.