I suggest a less common map. (variation of #4)
Halo has distinct areas which are difficult to get to from 1 place to another... you have some freedom of movement, but in general it is fairly linear.
Make the map to match.
The Humans start on the left most side. They can not travel west only east. (at least to start the game).
The flood starts in the middle, but are land locked and can not come out.
For example:
This allows humans on the left covenant on the right, flood in the middle.
Initially, they can not meet. Quick grow and the humans and covenant can loop around and fight each other... or if they dare, they can try and fight through the flood controlled region.
The flood workers are initially flagged as wheeled and so can not enter the mountains and so the flood can not escape for a while.
The humans and the covenant can initially not meet each other directly. They can loop around the flood, or they can fight through it.
They can eventually build bases on the other side of the mountains and there by build roads to cross over. This can be used in the late game strategy.
No units can have airlift. No units can have relocation. No railroads. This makes the game about moving moderately from your base to your foe.... more like halo.
---
btw: I hope you know this is gonna be a slow time consuming thing.