If you look hard enough, even some 512MB video cards aren't THAT terrible in price. As Slashmire said, NVIDIA is a good choice for cards. The thing with 512MB cards is the the massive size the actual cards have. They have been known to steal another adjacent slot next to it because it's so big.

51MB cards aren't really mainstream yet, its the 256MB ones. The 512's are becoming popular fast and there are some people that have dual cards (2 x 256MB cards)

Remember, the video card isn't the only major factor that will determine the performance of your games/3D applications.