well, i'm still a bit skeptical. I haven't had enough naval battles yet, but from what I've seen they still appear quite a bit random... for instance, I had 3 biremes (2 + 1) vs one single AI ship (bireme, no-stars admiral). I reloaded the game for more than a dozen times, but in no combination or way was I able to defeat the AI - not even once.
All ships were full crew (mine and AI's) in the beginning, nobody had any stars.
But I lost consistently (although sometimes it was a close defeat, sometimes a clear defeat, etc).

What gives ? It looked to me like the same "pity" algorithm from MTW was implemented in Rome as well - kick AI's butt on land, you lose naval battles; lose on land, you get really lucky at sea... (because I had had 2 battles that turn, both crushing the AI).