On many maps going first can give a big advantage.
I would propose that prior to the first turn starting each player get to bid a portion of there starting gold to move first. This would be given to the other player as compensation for going second. In the event of a tie move order would be random as in the current system.