ZZFH is correct. I had an AMD64 X2 4200+ and I had it at 800x600 with all details off and it struggled to stay around 25 fps.
I recently upgraded to an AMD Phenom II X3 720 and on my lowly ATI HD3870 Radeon, I'm running at 1280x1024 with most graphical options turned on and the game is VERY smooth, and that's on just three cores.
I've since unlocked the fourth core in my CPU (with no issues so far!) and the game runs pretty much the same as far as I can tell. I still can't play at the highest settings (I think I'm GPU bound now), but with what you have, the game will be barely playable and it will look like crap.
If you go AMD, get the Phenom instead. The Athlon II's do not have an L3 cache which hurts performance.
Overall, the Intel's run better, but if you are budget minded, then AMD won't hurt you either.
Like I said, I'm running on an AMD64 Phenom II X3 720 Black Edition. With just 3 cores, GTA IV runs pretty darn good at just about the highest settings. When I ran the benchmark, I get an average of 38.9 FPS with 88% CPU utilization (which just goes to show how badly optimized this game really is). I'm sure my FPS would go up more if I upgraded my HD3870, but for now, it works just fine.
So either a Phenom II (X3 or X4) or an iCore 3 should do you just fine.
If you get the X3 720, it's got an unlocked multiplier so overclocking is VERY easy with this chip. Also, you MIGHT get lucky (like I did) and be able to unlock the 4th core and it will be stable. Mine has been.