Interesting question, I don't have a fit all size solution for you but I have some thoughts about the steps to take to make it fair for both teams. First creating the perfect maze.
Carving out the maze step by step for both the red team and the blue team simultaneously should fix the issue of more/less cells closer and thus having more options to choose from for one team making it harder to solve. There are still cases where one team has no more room of carving out walls because the other team has "cut off" an area. You could implement a "switching" patter where the team without cells left can "steal" cells from the other team.
Another much simpler approach would be to randomly pick a common end point for both teams then have both teams walk away from it randomly but in a different pattern. If you use an equal amount of steps in a perfect maze this should also give an equal amount. Team could end up very close together but you can have a check for this in place and regenerate if necessary.
However, when you start from a imperfect maze or randomly remove walls the problem will get a lot harder to solve. So once you have placed the teams fairly in the perfect maze you could do the following.
You should not carve into the other teams area unless both cells have the same amount of distance from there starting point.
Second you should carve only into similar patterns otherwise one player would get a bigger loop, making it unfair.