I hate how overconnected they are,
I don't consider this a problem, but IIRC (can't check from here) that should be addressable in the map generation settings.
Nope. Not even a little; there's nothing in settings that addresses connectivity.
It's not just about chokepoints; it's also about spacing between capitals. This is a point which has been discussed around here for a while, though I've only seen passing mention on other forums (though said mentions agreed with the conclusions).
High average province connection reduces the number of players that a map can practically support noticeably. It's most obvious with very densely connected maps like the hex ones (or honestly any by Pymous), but any higher-connectivity maps (of the sort that during Dom4 increasingly supplanted the sparser maps that were more common through Dom3 - I'm very tempted to blame Dom4's introduction of ritual ranges for this) can reduce the distance between capitals to an absurd level. The other Dom5 game running here right now (on a standard random map; 192/33 for 13 players) had three nations start w/in 1 province of the other two. The more densely connected maps have a tendency to have some players clustered closer together than others, which makes for death by random geography even moreso than usual. It's really obnoxious to lose before the game begins. (As an aside, it also reduces some strategic play by e.g. rendering ritual ranges and map move speed less significant.)
Basically, the more densely connected a map is, the more provinces per player are required to create good spacing because it's easier to trace shorter paths from any given province to any other. Consider the two extreme edge cases: a fully connected map with 20 provinces per player necessarily has 0 provinces between all capitals (and everyone can always directly attack anyone, and ritual range/map move is effectively simplified to 0 or not-0), while a contiguous map with 20 per player where connections = 2 for all provinces (a giant ring) can have 19 provinces between every player (and every player can only ever directly attack 2 other players, and ritual range and map move are
very important). What "good spacing" comprises is subjective, but the random map generator does not tend to make sparse enough maps that "traditional" province counts like 15 or 20 aren't going to make for very close starting positions (for some players, but not all) once thrones start cluttering things.
and 2) there's an awful lot of water-wanting nations
How's that a problem for random maps? You can freely set the water percentage.
You're correct that's not a problem with random maps, but it
is a problem with the proposed "bogstandart 15 provinces per player random map". Once we start fiddling with settings, we're not doing bog-standard.
I think giving the full allotment of provinces is overkill even for fully aquatic nations (aside from EA R'lyeh) and we should have about a third of the provinces aquatic.
I'd not dream of suggesting full allotment. For reference, the map I suggested is 155/35; my point was that we probably don't want a map as dry as many are. We want a lot of coast as much or more than a lot of water.
You might be right about going with a third, though, if we're doing random (which I'm still leery of doing). Based on a few tests, I'd say 50% water/200% UW province size feels the best to me, though I can see some value in 33/100. 66/400 seems like the map generator has trouble doing it well, and it just really looks off for the number of wet nations, even realizing the map gen is often doing less than 1/3 wet at that point.
I'd also argue for bumping the cave percentage to 10. 10% seems to give 3 to 6 caves (of 180) rather than the standard 3%'s 1 to 1 caves.
In any case, "re-make the map 'til something palatable-looking shows up" is probably a necessity if we're doing random.
[Edit: on reflection, I really don't think we want to go as high as 1/3 the provinces UW. 1/5 or at absolute most 1/4 water will probably be plenty. Coasts and a few "deep" provinces are more desirable than large seas with many provinces not touching land... and if we go with random, it'll be a lot harder to get that with 1/3 rather than something less dramatic...]