I have a great gaming computer and just bought GTA IV on sale at Wal-Mart for $10. I installed it, updated it, and attempted to play. The problem is it's supper laggy in the menus. It takes 5-6 secs for the mouse point to move after I've moved it. It can even start the actually gameplay. I don't have any mods installed.
Make sure that the game is patched to version 18.104.22.168 at least. GTA IV was extremely buggy on release, and unpatched it might not be playable. You may also have Crossfire issues that are causing the game to run slow. Download the Catalyst Application Profile for GTA IV, and install it. Failing that, try disabling Crossfire and run the game with just one card.