-Rethink the turn system, perhaps instead of letting the side with initiative move all his units first only let him move a fraction of his units before the enemy side can move a fraction of theirs. The more of an initiative advantage a side has, the more units he gets to move towards the start of combat
MOO2 had a Ship Initiative option. Combat order was determined by each ship's beam attack rating and combat speed.
You're correct but in practice the vast majority of the time one side has higher initiative for all of his fleet, or at least a majority of it -- especially against the AI.
For the benefit of simplicity imagine each side is comprised of homogeneous ships, with one side having a single point more initiative. My solution would be to let the side with more initiative begin moving his forces first, and generally move a few more units each time than his opponent. On the other hand, if the one side has ten points more initiative he can move a far larger portion of his fleet than his opponent (at the earlier stages of a combat round of course, as by the end of the round both sides have moved the entirety of their forces).
Of course heterogeneous fleet composition where different ships feature different levels of initiative complicates things, but it should be possible to combine the two systems.
MoO1 sidestepped the issue by starting all the ships out of range (until you got teleporters).
With the exception of BHG MoO 1 also didn't scale ships' offensive capabilities so much farther than defensive capabilities at late game, which helped the side with higher initiative not have too overwhelming of an advantage. Teleporters could be an issue sometimes, but there's a good chance everyone has interdictors when you get to the far late game. BHG + teleporters in a game without interdictors was pretty overpowering.