Without lowering your graphics
Right-click on GTA 4 in Steam, and click on Properties.
Click on Set Launch Options... and a window with a TextBox will appear.
In that TextBox, paste these arguments:
and GTA 4 should run with a huge speedup.
On my rig
32 GB RAM
GeForce GTX 680
GTA used to run on max settings at around 20-35 FPS.
With these arguments, it runs between 50 and 55 FPS and averages at ~52 FPS.
With lowering your graphics
Interestingly, GTA doesn't seem to care about GPU so much, as there is almost no difference between playing with a 1920x1080 or 800x600 resolution.
The only settings that seem to yield any significant increase in FPS is
View Distance and
Detail Distance, which should be lowered together. With both set to 1, my max FPS went from 55 to 140, although the average FPS only increased from 52 to 55. I wouldn't recommend setting them both to 1, as it can introduce some odd graphical glitches, such as signs seemingly floating in midair, until you get close enough for the sign's support to pop into view.
You might want to set the ingame option
Definition: On, which will deactivate Motion Blur (yes, On == deactivate) and earn you an additional 5-20 FPS when driving fast enough for aforementioned Motion Blur to kick in.
About why GTA fails to start
According to this wiki the problem may be caused by an out-of-date GFWL client, or because of your MTU size.