It'd be nice if fleets could have a little more autonomy from cities. My suggestion would be to allow them to move to any location on the map instead of just cities, stay in place and act as a point that you could send ships to and from, same applies to enemy ships and fleets. Being able to attack an enemy fleet while crossing the ocean before getting to your lands would be nice and the AI could do the same. Perhaps introduce some kind of supply concept where ships have to dock with a friendly city every so often or they might be stranded or crash. Maybe when new ships reach the fleet it averages out supplies so you could keep sending ships full of supplies to refresh the fleet without having to return the whole fleet to port.
I definitely like this. Will have to figure out how to make it work and easy to understand from a UI/game rules perspective.