This looks like a nice idea for a new kind of terrain "potato field". Move cost -4 for heroes -1 for turn 1 units and -2 for all other units. This is the terrain where basic units pass through easily.
But seriously, the only way to balance starting advantage is with roughness of terrain and/or toughness of neutrals. If neutrals are weak and terrain smooth, starting player has big advantage. If terrain is rough and neutrals are tough than starting advantage diminishes but the game last longer.
For the maps with difficult terrain, it is possible to get a strategically win game by turn 20 and still can't capture the last city by turn 40. So I was suggesting adjudications by request after turn 25. May not be fair but a good way to speed up.