Well I suppose that's the odd part. GTA3 didn't have this problem that I can remember, although I may have turned that down to its lowest settings as well. I haven't played it for quite a while. I also don't play games very often. The last one was Warcraft 3, but I don't imagine that that game is more taxing on the system than Vice City.
_________________________
Matt