Having contested bases doesn't really affect the fairness of the map at all. Maps with contested bases can be balanced so that each side gets to one base first and each side has an even chance of capturing a base. The main problem with contested bases has to do with the "fun factor" of the map.
As you noted, whoever has the base advantage is almost guaranteed to win the game. Even if you manage to capture a neutral base just a day or two ahead of your opponent, that unit advantage is often enough to be decisive. Not to mention the advantage if you are able to gain a base advantage over your opponent for more than a couple days. This is especially true in high-level matches where even the smallest discrepancies in unit count or funding can be ruthlessly taken advantage of. So because of the importance of the bases, the entire game is based on who can execute the early game the best and gain a base advantage. On most maps the game turns into finding the "perfect" way to open the game to capture a base first and prevent your opponent from getting theirs, and that just isn't much fun compared to a normal game without contested bases. The entire game is decided in the first few days, and the smallest of mistakes can mean certain defeat.
So for casual, lower-level games there's nothing wrong with contested bases. But for competitive, high-level maps it can be a pretty big deal, and that's why I commented about it on the map you linked. I hope that answers your question.