This would be cool. I agree absolutely. Sailing ships and or runic iron clads full of elves or lizard men or whatever Rules for wind magic and "greek" fire. And sea monsters of course. And all with the well known and great starmada basic system where you can construct your ships by yourself.
For example Spartan Games recently developed Uncharted Seas, a miniature fantasy naval game. Personally I dont like the rules very much, but its success shows that such a game is cool today by young ( and older) gamers.
Spartan Games also developed a steampunk naval game with flying fighter fortresses (like in the movie Sky Captain and the World of Tomorrow). The minis are looking very good in this. Its called Distopian Wars.
http://www.spartangames.co.uk/dystopian_wars_federated_states_intro.html
and
http://www.spartangames.co.uk/elf_fleet.htm
What do you think Dan? Is it possible that we will see a naval game along the lines of fantasy or steampunk in the future?