What might be interesting is to give some weaker units (like destroyers) a very high withdraw chance. It might be interesting to allow such units to attack and always be able to safely withdraw. Even though they can't win battles then, they could whittle the enemy down without fear of sinking.
I had an idea in relation to the original problem this thread posed, namely being able to send landing ships straight past waiting defending battleships. How about a significantly increased visibility range for ships? Then you would be more likely to see enemy navies earlier, before they got to your coast. It would be quite reasonable I think for newer faster ships to have extra inherent visibility range than ancient wooden canoes. Perhaps we could think of such a 'large' visibility range as a quasi-patrol function.
These two are really good ideas.