What about each team picking and locking one ship prior match (without each other knowing what they pick ofc)? And then they can choose whatever they want for second ship once they get in a lobby. So that wouldn't make things too complicated and limited, but still limited enough so there wouldn't be endless ship swapping on both sides and would still require some thinking and strategizing depends on the map and enemy you're facing.
This would equally limit both teams and give them enough freedom (with second choice) to decide if they want to choose a counter to enemy or pick a support to their ally or whatever.
Like people already said, complicating too much might just turn it into a mess and not fun experience, so I think this idea wouldn't limit any teams too much, but enough to think about what they will pick and unable them to freely swap both their ships 10x in lobby.
EDIT:
Also
The game is already won in the lobby in most cases, so you might as well make the lobby strategy more interesting. But who cares what a casual scrub thinks.
Just curious... Are you related to Cerersbane? If not, you gotta be at least best buddies?