Regarding the memory question, in my case, for all current games that I play, a 256MB card gives me no significant advantage over a 128 MB card. For example, I run at 1280x1024 resolution with my settings at the highest quality levels allowed for UT2004. 128MB of memory is adequate for these settings with every map I have ever played. (My card is an ATI Radeon 9800 Pro, 128MB.)
Personally, I would choose the horsepower over the memory if you are playing at resolutions in the same ballpark as mine, you are not trying to run multiple displays, and you are not running with AA on at high resolutions. The extra memory is not being used.
As displays are getting larger, as people are beginning to run multiple displays, and as the GPUs are able to drive AA at decent framerates at high resolutions, then the extra memory begins to be more useful.
You probably know all this. There are different approaches used for AA with cards, but generally and in simple terms, a frame is "painted" at 4 times (assuming 4XAA) the final size you want, then it is scaled down and given to you. That scaling down process makes the anti-aliasing possible. The memory requirements for doing this exponentially increase by a factor of 2, so you can see that a huge amount of memory can be needed as the resolution and amount of AA you are trying to apply increases.
I did see benchmarks months ago that compared the 128MB version and the 256MB version of my card, and there was virtually no difference in performance until the resolution, texture quality, map size, and AA were set to insane levels. But, by then, the GPU really didn't have the power to drive the system at framerates that you would probably want to play a game at.
Like I said before, the thing you want to avoid is having to page information in and out of the card memory during game play. If the settings you are going to be playing at do not exceed 128MB, then you are good to go with that amount of memory, and anything above that is just waiting for your next upgrade.
Hopefully that helps answer the question a little for you.