Perhaps a map where you're conquering the bodies of water rather than the land? There are enough to do it, including segmenting the mains. (such as Bering Sea/South China Sea being small parts of Pacific, etc.) Could use rivers to connect certain areas....I'm not a cartographer, so I don't really know how you'd work out the kinks, but it's an idea.
And even though they'd still be called "armies", I guess they'd be "navies" or "ships", huh?
