Larger combat map with a limitation on ship numbers in combat.
Have ship combat based like ground combat, so many turns of combat per game turn. This will allow for retreat and reinforcement of fleet elements (especially if there are limits imposed as to number of ships in combat) between turns. It will also make fighters more valuable as an attrition unit.
Eliminate formations as they are only used in setup. After that they are useless.