No two maps are created entirely equal... if every map had to look as good as the best looking CC map, we'd only have one map. Vancouver is a beautiful map in its own right, and is on the road to completion.
As for this map, the biggest gameplay issue seems to be the way territories connect. I agree that if you read the legend everything is fine, but its become obvious that many people do not bother to read it and are then turned off by the amp. You can lead a horse to water but you can't make him drink, right?
However, as the mapmaker you can lead a horse to a muddy cesspool of disease, or to a crystal blue oasis. While I don't think this map should be overhauled to rework the arrows, I think you (gimil) could take some little steps to make players more likely to notice/access the legend and the arrows/
For starters, I have never liked (and I've said this a few times) that in some places on the image the text is transparent with a grey border, in some places it is black with a white border, and the arrows are a transparent grey with a litghter grey border. For me this has two results: 1) some elements seem more important that other elements, and 2) the image is not clean and balanced. By far the easiest on the eye and thus the most accessible text on the map are the territory titles - and they should be. But the arrows are given much less prominence than the territory titles and as a result are kind of lost in the image.
Next, the text in the top right legend in uninviting. The white stroke on the letters makes the text run together, and its something of a chore to read. Knock the stroke down a point - and perhaps make everything a point size smaller - and the eye can fix itself on the text more easily. And since the part about Land and Sea do not connect is what folks are failing to read maybe that should be first, or somehow more prominent?
And this is the last time I'll say that if the text in the two legends were given the same weight the map would be more visually in balance.
And since the land/sea borders are impassable, have you given any thought to upping the thickness of the borders by a pixel? Right now they are the same weight as the conventional borders between territories, leading to confusion.