I fully agree with KGB! Our own 2vs2 team game actually confirms it pretty much. Having the starting locations in the middle of each territory would be much better.
However, I am not yet sure where they ought to be. Having yellow start in Khairat, which looks like a nice spot, would probably be too much. Likewise moving cyan west is difficult, since the terrain doesn't allow many choices, and picking Corrinis seems too good for Cyan.
As for the desert road: Yes and no
Khairat is much more vulnerable from sea now, which might be a good or bad thing. I just wanted to discuss the issue, not requesting a change. Anyway, I seem to like it and I guess I would like it even more if the city of Nedschef would be moved one square to the east. It does not change the distance tot he other cities (one has to walk around the river anyway), but it would make it impossible to invade by boat in a single turn (unless one brings a sandworm along on boat). Since Nedschef would still be directly adjacent to the river, it remains vulnerable to kraken and serpents, unlike its neighbour cities. So one city is vulnerable to sea creatures, and the other one to boats, making it somewhat asymmetric, which I believe is good for maps.