Naval regions always made the most sense to me. They'd still be big, though, say like having a total of 3 naval regions between Golden Farrow and Port Raviel.
Having various ship options in the travel page for eveyone, requiring money, would be equally interesting. Especially if these options rely on building a shipyard in your port. It starts to get complicated at this point, though.
