Make sure that you don't have any browser windows open in the background, especially Chrome. For some reason Chrome makes even the menu quite laggy.
The game generates a detailed 3d galaxy just for the menu. If I were you I'd disable the 3d rendering for the menu to improve performance.
C:\Documents and Settings\<YOUR USER NAME>\Local Settings\Application Data\Ironclad Games\Sins of a Solar Empire\Setting\user.setting
(that's the location on XP; it's in a similar but not identical location on Vista and 7)
to FALSE instead of TRUE by using notepad.
Is the game itself unplayable? I usually play small maps, and the menu (when in 3d) seems to lag a whole lot more than when I'm actually ingame.
Obviously, other solutions would be to disable all of the special effects and to reduce the quality, and to disable antivirus and exit other resource-hogging background programs like Impulse and Steam...