Granted, it's possible to conquer Russia starting with Tuscany or Münster, while the AI usually stagnates, when it is not annexed by neighbours, but when you think about it, within a few centuries, Rome went from a single city with powerful and not quite friendly neighbours (they would say 756 BC, if my memory is right) to hegemony over Italy and the Mediterranean by the 2nd century BC, and a EU game starts when some kind of basis for power has been founded, not when your original leader kills his twin. Genghis Khan conquered most of Asia within one lifetime, and he didn't actually rule anything during most of it. You're basically supposed to create a new Rome or a new Mongol Empire in similar games, it's the point of the game. So while the AI can be improved, it's no much more stupid or ineffective than some historical human leaders really were.
However, I don't like to see that it is so easy to control separate pieces of land, even without massive (or even marginal) naval superiority. When the AI faces an ennemy of similar military might, it should be more focused on where a threat exists, and use initiative only on meaningful targets if faced with them. Landing 5k soldiers in Danish-controlled Gotland should not happened when you're losing Stockholm and risk having the rest of your army routed. Also, I'm not really bent on colonizing, so I don't know much about what happens in the New World, but from what I have seen, the AI either has 90% of its army in the Americas, or none at all, same with the navy. With a relatively peaceful Denmark, I conquered most of Great Britain because all the fleet was God knows where, and only a few units where in England, and in another game, I saw several doomstacks around the coast of Spanish South America, representing most of Spain's military, though no war took place, to later walk by in their lands with only 5k cavalry, with no sign of danger. I don't know how the AI chooses where to wage war or to place troops when there are several possible areas, so I don't know how difficult changes would be (though I don't think it's a very easy proposal to tackle on, because several 2k armies in every single island is not much better), but it's the only think I'd like to see that would help a more realistic and difficult experience. It would give a more plausible result to expeditions such as that of Scipio Africanus, either in the place of the Roman Republic, or that of the Carthaginians.
And I also think some part of randomization at some point in the process would be good, though I don't know how it could be implemented easily or dynamically.
About the small fleet attacked with small fleet * 2 problem... If it sees 4 galleys of their coast, and attacks it with all their 15, and you can just send in 50 galleons to destroy them, I think it's better than them losing only 8 to the operation (even though the player can just rinse and repeat until the same result happens). I haven't observed that problem, though.