Think of combat as rolling dice, if it's 20 sided or 6, you still have the chance to roll a one. Just because your attack value is higher than the defense of the AI, or vice versa, it doesn't guarantee that the better unit will win, just that they have a better chance of it. Granted that sometimes unrealistic results occur (I just lost a battleship to a galleon, oh well), but thats how the game works, so play accordingly. I'm pretty sure that there is no "cheating" going on with the AI combat, as I've also taken out a rifleman with a horseman and had several other fortunate battle results.
As far as problems with the romans are concerned, I didn't have any myself. I started out building a settler in Athens, thinking that if barbs did show up, the most I would lose is a little gold. my worker built a road on towards where I was going to build my next city (up by the cow). I had though I was going to build sparta on the jungle to auto clear a space, but when I saw the gold I built on it. Then from both sparta and athens I just rotated between hoplites and settlers. My next 2 cities were set to just build workers, as they both grew in 10 turns, and both could build a worker in 10. I think having lots of workers early on is great if you are planning on building, as the AI views them as military units, and judges your power based on number of military. Each settler had a hoplite to escort it, and then the hoplites would go out and explore as the next hoplite/settler combo pushed passed the borders of my territory. I used warriors for garison units in areas that were safe (inner cities), and always kept extra hoplites on mountains and hills in areas I hadn't settled yet. Most of my cities built 2 or 3 workers before switching to the hoplite/settler rotation, and I was able to still keep pace with the Roman expansion for the most part. I think by the time they had built their 10th city, I had 9, with 3 settlers on their way to city sites. Every time I got a tech, I traded it to the Romans instantly, so they wouldn't research the same thing as I did. I bought all the techs that the Romans got first, and traded maps freely. From a research perspective I went for writing first, with as low a percentage as possible (takes 32 turns no matter what). Then I went for pottery, at 100% as it could be researched in 8 turns I think. I got 2 techs from huts, and 2 more by trading writing and the hut techs to the Romans. After Pottery I decided on Mapmaking, as by then I had pretty much explored all but the Roman portion of the continent, and figured it was just me and Caesar till I could send out some galleys.
After sending out several galleys (some were sunk by barb ships, blah) I realized that without the lighthouse I was alone, so started it immediately after a temple was built in sparta. All the other cities were still on the hoplite/settler rotation except for Athens which had switched to just settler settler settler (it grows to 3 in the exact time it takes to build a settler with a wheat and grassland). Soon I had most of the upper 2/3rds of the continent, and switched to rush building barracks in all the the less productive ones. I had settled on Iron and had 1 horse, so once barracks were build I started rushing out horsemen from all but 8 or so cities that I built temples and librarys in along the Roman border. I finally finished the lighthouse about 100AD I think, and sent my galleys out to make contact. I found that I was only about 2 techs behind the leaders, and with my treasury of 3000 or so, was able to easily buy the ones I didn't have. I was intent on wiping out the romans, as they had started demanding maps and gold, so I didn't give contact to anyone. Also I kept the Aztecs Isolated, as I wanted to take their Island once the Romans had been eliminated.
Before the war started, I had 50 horsemen, about 10 extra settlers for refounding cities, 2 Roman cities had defected already. I split my horsemen up into 3 groups, 2 of 20, with a few hoplites and settlers along to claim territory, and the other 10 for homeland defense (Caesar had LOTS of troops wandering around my territory). All my coastal cities (I only had about 4 at this point) were building galleys for the Aztec invasion.
I think it was about 500AD when I struck the first blow, razing 3 Roman cities on the first turn of the offensive, and building 2 of my own in their places. Rome had built the Pyramids, so that was the only city I planned on not razing. Rome didn't have anything I wanted, so I didnt sue for peace, just kept right on rolling. After the first couple of turns the Roman army had been wiped out, hoplites were stationed on the horses in his territory, and 10 new horsemen were headed to the front. Tech wise I was just into the Middle ages, and I researched Theology and Edjucation first, as I guessed the others would go for Feudalism and Chivalry. I wanted to wait for Chivalry and Knights to invade the Aztecs, so purposely allowed the war with Rome to be prolonged. This had a great side effect of giving me my first Great Leader, who was promptly made into a Knight army (for heroic epic). I took Rome close to last, as I didn't want it to revert culturally. All the others I razed, giving me close to 30 captured Roman workers.
And well, that's how I delt with Caesar. I think the important parts are to stay close in number of cities and number of units (counting workers). Even then they will start to make demands once the room to expand runs out, so make sure to have a large army, and if at all possible, keep the Iron out of Rome's grasp. Massed horsemen, with hoplite support, really makes of mess of the Romans. I think its better to raze than to try to quell resistance. It allows your army to keep moving, just make sure to have extra settlers to fill up the space, as barbarians will pop up if you don't. The biggest and toughest battle of the Roman war was the 24 barbarian horsemen who showed up near the end.
For the Aztec invasion, I loaded up every spare Hoplite, upgraded all non-elite Horsemen to Knights, took about 5 settlers with me on the first armada, and set sail for their island. The Aztecs hadn't built any wonders, so I planned on razing everything. About this time the AI researched Astronomy, so I gave contact with the Aztecs to everyone, and planned on an honorable genocide

This gave the Aztecs Gunpowder the next turn, so was a bad idea, as I should have put off giving contact to the Aztecs to anyone for as long as possible. It didn't matter much, as the whole Island fell in 10 turns, though the Musketmen probably cost me a Great Leader. I was using my elite horsemen to do most of the killing, with the Knights there just for support and to weaken the defenders. But even with 1 hp left, the Musketmen would often kill my elite Horsemen

So I ended up just beating them down with my Knights. A few turns later I had colonized the whole of the island, and decided to turn it into a settler factory.
I'm currently about halfway through the conquest of the main Continent, with about 1/3rd of it re-settled. My original Continent is a terrible mess of pollution, as its too inane and nerve wracking to manually put each worker on the polution square to clear it, and with the patch (that I installed after the Aztecs were taken out), it doesn't seem to let you use shift-p after 2 workers are already on each pollution square. All my cities have recycling centers and mass transits on the original Continent, but still I get 5 to 20 new pollution squares every turn, and am slowly falling behind on the cleanup. My navy is horrendous, as every battleship I build gets sunk on its first fight (Galleons, Ironclads, Destroyers, anything kills my battleships, haha), so I just gave up. I'm the only one with Modern Armor or Mechanical Infantry, and am spearheading invasions towards all oil and rubber sources already not in my control. I had tried an invasion with just calvary (my upgraded aztec army) earlier in the game, but after wiping out the Indians and Germans my offensive stalled as everyone else had gotten Nationalism by that time. I formed a coallition against the Japanese and Chinese, but by the time I made it to the front, the French, English, and Russians had basically finished the war. So I sent the 30 or so settlers I had to grab up every free space, and took control of almost all of the resources on the continent, but that really made the English mad at me, and all my newly founded cities were wiped out within a couple turns. I did manage another Great Leader in the quick war with the English, and am saving him to rebuild my palace on the main Continent once I am done with the conquest. I plan on giving cities on the Aztec island away so that I can have the main 2 continents all to myself.
I have about 200 captured workers from all the razed cities, and had about 200 more that I added to my population already. If only there was an easy way I could put them on pollution patrol

When I try to clean up all the pollution in 1 turn, I can, but it takes about 15-20 minutes to put all the workers to work, and the pollution comes back every turn. If you haven't installed the patch yet, I highly recommend that you don't, if only for this one reason. The reduced corruption, and having police stations also fight corruption is nice, but the automation of the workers is really awful.