My 2-year old HD4890 plays that game great at 1920x1080, with eye-candy enabled. As megaman hinted to, GTAIV is coded poorly, and shows CPU-dependency for it's in-game physics calculations. As such, the GPU doesn't truly dictate how well it plays. So unless your monitor is of greater resolution than mine, anything comparable to a 4890 (5770/6770, GTX275) or better (6850, GTX460 and higher) would play that game fantastically when coupled with your CPU.
GTX460 1GB cards can still be found for around $150 before rebates, making it a very solid performer at a reasonable price. I do prefer it's replacement GTX560, though, which is a streamlined version of the 460. It's capable of higher clock speeds while consuming less power, but they tend to cost about $190+. The rival AMD alternative would be the 6870 at about $180. These are all pre-rebate prices, and it should be noted that many video cards in this performance range carry rebates between $15 and $30.