Toshiba Qosmio X300Dunno, we don't know anything about your PC.
I upgraded 4GB to 8GB RAM. Not only stutters fixed but also FPS boosted significantly. I am getting 35 FPS above on high settings now.FusionFix might help.
Try launching game directly from executable in gta 4 folder. Limit fps to 45, I found cutscenes were much smoother since they're recorded at 30fps but 30fps is too low for game play, 45 is ok.
Stutters becomes much less as you progress further into the game.