If we really, really want to add a third typing to the evolution chain, Flying is the ONLY one I can imagine working, mostly because of the movepool. However, I would have to see a really compelling concept before I voted for it to understand why it would lose its wing/sails as it grows in power, which feels pretty counterintuitive to me. Also, similar to how EpicUmbreon pointed out that no current pokemon loses a Dragon type upon evolution, there is just one pokemon (Scyther) that loses its Flying type upon (non-Mega) evolution, and that's very much tied in to the manner of its evolution (puts on a Metal Coat, and it's suddenly too heavy to fly.) So unless we have a really good design for a Flying type prevo that makes logical sense as to why it would give up its wings/sails, I'm still firmly in the camp of Water or Water/Steel.
Edit: I just wanted to add that to be perfectly honest, ever since I saw Naviathan's art in the submissions thread, I always thought it would have been just that much cooler if it DID have wings that formed a mainsail, and would even make more sense that way, as viking ships were generally sailing ships. If that were the case, I would also be very excited about the idea of having a sort of light schooner or yacht as a prevo that was Water/Flying, and it could even evolve, like Scyther, via Metal Coat. But sadly, Naviathan doesn't have wings (as they would look too draconic for a non-Dragon type,) and for that reason I just can't see it's prevo having them.