I was actually thinking Joao II myself. I havent played him other than a BOTM with the worst starting land I have ever, seen, LOL, but his UU is nice for early water warfare, and he starts with Fishing and Mining, which is pretty sweet.
I was also thinking about the map. Arch is ok, but how about considering Medium and Small, islands mixed in, and High seas? Makes for some reasonable sized landmasses but still a whole lot of water.
So, for possible leaders we have:
Hannibal (he sees a lot of action, UU doesnt "fit" well, though)
Roosevelt (I LOVE the GLH-Colossus with this guy, great late-game leader, can bring a LOT of bad positions back from the brink, strong early game too for key Wonders)
Joao (has the best UU IMHO for this type of map, EXP/IMP are 2 traits I dont think we have played yet, either)
Willem (sees a lot of action too, IMHO the best all around Water Map leader, would be the easiest, I think, for those thinking about stepping up a level)
BTW because of the problems with the AIs being properly handicapped from the WB, you should all be aware that Monarch with these games is "Monarch Light". The AIs dont start with Archery or Archers as they would in a regular Monarch game. You will still have the slower tech-production than the AIs, and lower Happy and Health limits, same as other Monarch games, but the starting bonuses arent as big as they normally would be. Game will be coming out in a couple days, so make your votes now (If you havent, I see some preferences, if you change your minds, no worries, post your ideas)
I would lean away from the FIN leaders, as they are really powerful on water maps. Plus we have played a FIN, and the recent PYL game was all FIN leaders. I like Roos or Joao, each has his strengths.
Map choices are:
Snakey continents
Archpalegio
Medium and Small