Disclaimer: I look for two things in my video card: gaming performance and MPEG-2 quality. The information may not be helpful to non-gamers.
I'm currently researching a new video card, and I'm currently eyeing video cards featuring the nVidia GeForce 6800GT GPU. That card's close enough to top-of-the-line, below the 7800GT, and can hold up well for the next generation of games. It also appears to have good value-for-price.
128 MB of RAM? Well, some of the high-end video cards are starting to come in 256 and 512 megs now. Memory is needed for all those textures loaded into the game, among other tasks. However, I read somewhere that having 256 or more megs of RAM isn't being fully used by current games from some mag. I'd usually take it with a grain of salt, but based on my experiences playing stuff like F.E.A.R. demo and Half-Life 2, I didn't notice any performance boost because of higher capacity.
Price: well, I'd look towards PriceWatch and see what the online retailers are selling video cards for. Brick-and-mortar store typically have higher prices for video cards. For the 6800GT, a good deal would be *right now* under $300.
Also, did you mean vertex shader? I wouldn't solely buy video cards just because of shaders, but the GeForce 6 series (6XXX) and up have the latest Shader Model, 3.0. Relatively few games right now support it, but future games likely will.
All in all, my recommendation the GeForce 6800GT (not the plain ol' 6800) with 256 megs of RAM. Unfortunately, I don't any experience with these cards, as I'm stuck with the ATI Radeon 9600XT for the moment. Some hardware manufacturers produce these cards and may take out certain features, like slower clock and/or memory speeds.
Also, do you have an AGP or PCI-express (different from PCI) slot? Most folks have AGP, but more and more video cards are being made for PCI-e slots and AGP may be phased out in a few years.
Hope (some of?) this helps, although I'm just in "research mode" right now and lack the funds to get something cool and new.