Love the ideas. The cave thing would be awesome, as would the vertical height scenario. Though perhaps make it a bit larger. Perhaps make it so that the map size is a giant cylinder in essence, with objects jutting out on all sides at various heights, and perhaps make it large enough so that two ships can float at the same height level and open fire at each other (with wiggle room inbetween of course).
I guess the more I think of it, 1k km squared would do it. Correct me if I'm wrong, perhaps the middle section of Paritan (I mean the size of the big courtyard there), would be a good fit for a ship battle. I had enivisioned somehing a bit more compact though, as in only 2 ships (facing each other at the same height) and perhaps 100m of wiggle room total between the two ships would fill the diameter of the cylindrical map.
As far as scenario, how about a massive mining pit?