The 3850/3870 should be more than good enough for GTA IV at 1280x1024. 512+meg for anything higher than 1280x1024.
Or just wait for the 3870-X2/ 9800GTX, then you never need to worry about upgrading until GTA IV - part 3 is finished.
I agree with most, you need a new motherboard/CPU or that will be the bottleneck (not the video card). A low-end C2D will be more than good enough for now. Or a Yorkfield and you won't need to upgrade the CPU for many years to come.
The mobo sealboy suggests is a good one. If you want to overclock, then you should get a more high-end mobo with high-end RAM.
There is no GTA IV for the PC, I will just assume it will get ported like all previous GTA games.