One correction - if there's a 256Mb at a reasonable price, it'll probably be a really junk chipset (yeah, I know, I just got a GF4 MX440, the kind of "junk" that can be found as a 256MB, but the 128MB for 10 quid is 60% faster than what I had before).
I'd be wary of going as low as 64Mb, but 128 Mb on a better chipset would blow away 256Mb on a really bottom end chipset.
More important than 64/128/256 (we'll ignore 512Mb for now), is the DirectX hardware level of the chipset.
Nvidia:
TNT/TNT2 (don't laugh, you can still buy them) = DX6 - these days, gaming satisfaction =NIL
GeForce, 2, 2MX, 4 MX = DX7 - The hardware T&L engine is good - and hardware T&L is the bare minimum for a large number of games
Geforce 3 - The first DX8 card, and far superior to a 4 MX
Geforce 4 (all non-MX versions) - DX8 (and at one time, the major gaming powerbase)
Geforce FX - DX9, but the lower models can be too slow for it to be useful.
ATI Radeon:
7500 - DX7
8500 - DX8, and a one-time great that can be found cheap - the LE version is slower clocked, but doesn't lose much.
9000-9200 - still only DX8, and no real advance on the 8500 (apparently, the 9100 IS an 8500)
9500 and up - DX9 - the 9550 is a budget DX9 that may share the same "too slow to be useful" problem of the Geforce FX5200