Wind!
You can't have any kind of interesting seafaring without wind.
Even Ultima 3 had seafaring and ship to ship combat that took the wind into account and that was almost thirty years ago.
There needs to be a windrose on the map that displays wind direction and speed.
Different ships have different points of sailing.
Some can sail well before the wind, some can not sail against the wind at all.
Some may even have rowers.
Pirates! modeled that very well. See the Pirates! manual, search for GAZETTEER OF SHIPS
Hey, we could have a Ship Designer! (wonder where I had seen that before...)
And this being War of MAGIC, the elements will have a say in that, too. Air / Water / Fire are obvious candidates.
Earth seems a bit out of place but... where do you think tsunamis come from?
Well, tsunamis aren't exactly well suited for surgical strikes so you might make more enemies than you had planned on. =P
