I think this is the only time I would recommend an ATI over nVidia GFX card. Go for the X1600, pretty sure you'd see better performance in games. But don't expect blistering performance. But look into a nVidia 7600GS or 128MB 6600GT or 6800 if you could afford it, better than the 2 cards you picked!
That depends on how big the textures are, and how many textures there are in the game/program you are using. If you have tons of large textures, than the 128mb card will have to render them everytime you look at a different set of textures. With a 256mb card, you could have stored those other textures and you wouldn't have to render them again.
In a hypothetical example, I would rather have a 128MB 7900GT than a 512MB 6600GT. Memory makes a difference, but not as big a difference as CrazeD would have you believe. As for rendering, the card has to render everything displayed on-screen, regardless of whether it has the textures cached in the memory. So he has the right idea, just the wrong facts.