GTA3 can be a bit choppy, but you have to admit that the graphics, maps, and environment are first rate. I've spent days just exploring. The biggest problem with the game, IMHO, may have been that they were too ambitious.
Big hint: Leave the frame limiter ON. If you turn off the frame limiter, the game will become very choppy during times of intense action or whenever it has to calculate vehicle physics (whenever you're driving and you hit a bump), etc.
I'm certain that a patch will be forthcoming. Most of the people who are having problems have AMD cpu's (like myself) or WinXP (which I hate and went back to Win2kPro anyway).
/edit: thought I'd add (as kind of a footnote) that the problem is obviously the graphics engine. It has issues. Changing resolution or even hardware (I tested on both an XP2000+/Ti4400 system and a Tbird1.3G/GF2MX system) seems to make absolutely no difference in performance. Check the task manager, GTA3 doesn't always utilize the CPU 100% like it should (sometimes it does but sometimes, especially when it seem choppiest, it doesn't). Obviously, in famous T2 fashion, we are all in a big public BETA test again. :| Like I said, the biggest issue seems to be with AMD cpu's. People I talk to with Intels (particulary P3's in the 1GHz range) say the game runs great.