I'd be fine with Valanis. I thought it was important enough as a map for the community to go to the trouble of winterizing it, after all. :p
Since it's not a wrapped map, connectivity is immediately reduced dramatically - max distance b/tw two points on an unwrapped map is generally ~2/3s that of a 1D wrap or ~1/2 of a 2D wrap. I hadn't suggested Valanis b/c I've seen it held in contempt by a lot of people, but I've always liked it. The size is probably a bit better than Edowyn TBH.
If you want something that's more connected but not wrapped, I've always had a soft spot in my heart for Sharivar (because it's pretty). The province count is a bit higher than Valanis (and certainly Snerdyn) but lower than Edowyn. It's also less chokepointed than the original Dom2 or revised Dom3 version since rivers and mountains aren't perforce impassable. That's not on Steam, but the winterized/rivers/mountains/roads version I uploaded to Dominionmods was still available last I checked, and/or I could upload it to Steam myself, ugh. Sharivar would be best w/o any UW nation, but it can handle 1.
Well, of course a map with the wrong number of players will give unbalanced starts, without a map specifically generated to the number of players and the specific nations and with fixed starts you'll never get a really balanced start in a map.
The problem is that the number of players that are recommended for popular high-connectivity maps is pretty much still just derived from province count w/o accounting for how much worse the engine necessarily does w/start positions when connectivity is high. A highcon map will consistently produce worse starting positions than a lowcon map with the same number of provinces at the provinces/player numbers that are popular, b/c those numbers were fixed in the community's mind before Dom4, when connectivity was typically 2/3s what it is now with wrap being less common (but rituals had no range limits). It's easy to measure player load in terms of province per player, so the tendency has been to just kinda pretend that's the only relevant factor and assumed that if a map performs worse than expected for a given province/player count it's b/c the map is "bad" rather than considering the limits of that metric.
I feel tempted to blame the age-old issue of division of talents: creative people who can do the hard work of making the graphical map aren't necessarily the same abstruse people who can (or want to) do the hard work of calculating the obnoxious graph theory ramifications of how the maps are put together...