This is from my solo attempt as Rome on Diety level. (although I was obviously already aware of the map, etc. after playing in RBC3 on the Macedon team.) My strategy was to sieze the islands (Sicily, Sardinia, Corsica) in the first 10 turns, then build up in the north. After the 20th turn (I had an alliance I had to let end), I invaded the Celts, while gradually pushing into Spain vs. Carthage. Meanwhile, I used cats and some legions to beat back repeated landings on my islands, but did not attempt to invade North Africa until the end of the BC's. When I did invade, it was from both Spain and a landing in Libya near the Ivory, cutting him off from any new Numidians.
I did get caught up in a short, nervous war with Macedon, but was able to get peace without losing any cities, and a short war with the Goths where I counterattacked w/ heavy cav and took most of their cities. Carthage actually destroyed Egypt, and I had just fought across their at the end, and would have destroyed Carthage's last city (Gaza) on that turn, if I hadn't hit the domination limit.
A couple strategy tips, based on my experience and reading several accounts. First, keep Persia in check, by propping up Macedon if needed. Especially at higher levels, Persia can become a steamroller if you are not careful, and has access to lots of fertile land.
Second, while my normal instinct is to go for a decisive blow against a strong opponent like Carthage, I think going after their capital is actually counterproductive. It's initial location is somewhat isolated relative to the rest of their cities, once you take Sicily they only have half a core, and a limited FP. But if you take Carthage early, the capital tends to jump west, making both their coastal cities and southern Spain productive, and they can expand like crazy in Spain (Fertile, lots of resources) if they aren't hamstrung by corruption.
Finally, although they do have an advantage in fleets, a combination of galleys based on the islands and stacks of cats (and then fire cats), also on the islands, can create good kill ratios against his ships and eventually tip the balance. I tried to get 4-5 galleys, and a stack of 3-4 cats, on both sicily and Sardinia, and then hit his fleets when they would come for landings. (Also keep several legions/cav to counterattack his landing forces when they do arrive). After the cats weakened his ships, I could pick off the wounded and get back to port quicker than he could.
EDIT: Although ToA would be nice to have on this one, on higher levels it is difficult to beat the AI, since Persia and Macedon basically start in a GA the first turn. I focused on getting my Heroic Epic done by turn 11, armies rule in this game, especially heavy cav, and more leaders = more armies. Bacchanalia is definitely worth it though, and with a prebuild it should be easily achievable for Rome, as they have the easiest access to the right luxuries earlier than the others as well.