Cradle is much too big IMO.
Land of Legends has 13 provinces/player, which is just about right. I would be against going for anything much bigger than 15 per player. It's also good in terms of the small sea. I haven't looked at the start positions though (though they can be fixed of course); one alternative might be elmokki's other map:
http://forum.shrapnelgames.com/showthread.php?t=43180