Often I have FPS lag too, despite the fact my PC runs GTA IV well. Happens with many players around
you could try:
disabling any net-using programs, MSN and shiz
reducing game settings
set 'process priority' (whatever its called) in task manager to 'real-time'. Right click on gta_vc.exe, then do it
disabling 'frame limiter' in options while playing, only works on 1.9 script, also while it will delete the FPS lag, it will cause synch-lag instead. More than 30 FPS players aren't properly rendered in VCMP.
It's most likely server fault, due to transfering big amount of infos or similar.