AoI Difficulty

Send your scouts to each choke-point immediately and have them Sentry on the spot. Basically, you want them to keep the barbarians from thinking that they can come at your city (I guess the barb AI didn't learn the same lessons about choke-points that the general AI did). Exploration will have to come later, depending on your difficulty level.

Build a few warriors right away. You can send your initial spare warrior to one of the choke-points. I suggest at least two warriors at each choke-point (more for the highest difficulty levels). You can send an early warrior or your hero to that frostling den that is directly west. Other than that, I didn't push forth much at all.

Once you've secured the choke-points, then focus on two things: development of your valley and getting missile units. I build a city on the hill at the western choke-point next to the wheat, and eventually another city to the north, next to the 'lake', that will take advantage of the deer. Note that cities do not count as choke-points - barbs will assault them.

Another important improvement (besides mines, farms, cottages, and roads are forts on the choke-points. With the forested hill, your northern choke-point will have a defence rating of 100% and your units can use city defence promotions. My western choke-point is a mere 75% on the fort/forest.

The missile troops are needed because of their barrage ability. Having enough of these units protecting each front will almost ensure that you won't lose any units. And, once you start your push forward, they will be indispensable for softening up city defenders. But that's a different spoiler

horses, iron, copper the ship, etc. etc

That damn bird keeps wiping out the galleon if I move in too soon.

Are you using your heroe ? The game seems to love a heroic rush: even if you get unlucky, there are 2 backup heroes in store. The goal here is to kill a god! Play it like a quest: you're not supposed to spend time building stuff, the enemy civs are there to do that for you. No wasting time building cities and fine tuning ressources. No big stacks of units. No teching (all you need is forge).

The first time, picking Belenus, I concentrated on grabbing the copper resource and the northern barbarian city as quickly as possible (which I used as a strategy in my beta game with great success), and was promptly worn down by the flood of Mulcarn/Doviello/Barbarian forces, even while cranking out swords.

The second time, I didn't even make it out of the valley because a Doviello force was able to sneak in at the southwest pass and was able to get to my capitol. I saw my defeat video...

The third time, picking Epona, I turtled in the valley, and although I was able to hold off all invasions, I could not make any headway out of my valley after 200 turns - again because of the sheer number of invaders from both the west and the north. Even with barrage and fireball, I stood to lose more units than the enemy (based on the odds I was seeing), and would have been worn down by attrition. Perhaps I could have eventually broken out, but I do not like to play games which end up being an endless grind of attrition either.

So after thinking about it, the main key seemed to be - do not let the Doviello get strong. I picked Belenus. My strategy became focused on pillaging Doviello lands, hitting any lone units if they poked their heads out, and hitting the lightly defended Doviello cities - and this was important - razing those cities if I felt I could not hold them (this was important because whenever I normally play civ4, I have a house rule NOT to raze any cities).

Normally I would beeline to Bronze, because I focused on getting that copper resource, but instead, I beelined to Archery and Horses.

After sending Belenus and a couple warriors out into Doviello lands and doing some pillaging/hit and run, they doubled back and took the northern barbarian city. That city proceeded to crank out warriors, and then archers and went purely defensive. A large force of barbarians and Doviello units made that area a stalemate (I could not take out the Doviello units), but they could not crack me either - my goal was to build up experience points for those units.

Belanus and his small army proceeded south and redid the pillage/hit and run, and razing the Doviello city by the horse resource. They continued to patrol that area and further northward into Doviello lands to prevent Doviello expansion. They also managed to take out the Doviello city (and Lugh) by the northern copper resource.

This kept me from fighting a two-front war of attrition, which was what I ran into in my third failed attempt. Normally I would be beelining to that copper site too, but I concentrated on the horse instead because it was not subject to blizzards. All I needed to do was make sure that the Doviello would not reestablish themselves on that site. So Belenus continued to bounce from the north to the south on patrol.

In my valley, I built a second city by the wheat, and proceeded to create more archers while my capitol built a settler. A worker had been networking my cities with roads, and it built a road out to the horse. The archers and settler all headed west and met up with Belenus, and promptly built a city right on the horse resource. That city was able to quickly build horsemen, which went northward toward the copper. My worker proceeded to road up to that vacant copper site. I now have a settler en-route to that site, with a sizable force to defend it. Once I get swords, I will relieve the forces by my northern barbarian city, then based on what Belenus was able to see in his excursions into the remaining Doviello lands, I should be able to mop up the remaining cities.

I got overwhelmed my first game on Noble. I tried expanding/exploring early and my expansion city got destroyed and my second settler got captured. I got attacked by Doviello, Illians and barbs and that was that.

My second game, I still destroyed the barb city thinking that wasn't a good location which was a mistake. I warrior rushed the weaker Doviello city and destroyed it. Lost 1-2 decently upgraded city raider warriors trying to move to their capital. Instead, I found another city which was small and had Lugh in it. I attacked it with my lone upgraded city raider warrior and 5 crappy ones. I was surprised when they gave up and happily accepted.

I made a ton of additional mistakes as well.
1. I wasn't as aggressive in having Epona attack frostlings at the start. I'm at the end now and with 5 combat promotions, her fireball is really powerful. It made the game easier.
2. I built a city near the copper near the Doviello lands. I couldn't string irrigation to it so it languished as a size 2 city. The Doviello were my allies but they didn't irrigate to it so I was stuck. I also had to build a city on the same exact spot as the barb city I destroyed. I built a city a bit to the north. Blizzards destroyed the grasslands and I eventually just let the barbs have it.
3. I didn't beeline for archers. Swordsmen are kinda useless and I built quite a few. That city near the copper was also using up maintenance money and was size 2 until late in the game. I don't have maceman yet and I need quite a few turns still to get iron. I already have mammoth riders, though.
4. After I got the Doviello, I did some expanding/exploring and Mulcarn got big and destroyed my ally and I wasn't able to help that much.
5. I built quite a lot of catapults. They were only somewhat useful. Epona fireballs and archer barrage are decent substitutes. The building to produce them was expensive and took too long to build. I think I should've delayed getting them or not bother at all.

Eventually, I built a lot of longbowmen and crossbowmen and had a bit of a stalemate with Mulcarn. I was slowly gaining the upper hand when he sent his reinforcements to capture Doviello's last city instead. He lost quite a few units getting their capital so I was able to recapture it quickly and raze one of their cities. With the Doviello capital under my control, I was able to spread irrigation to my 2 other cities and grow them a bit, though it wasn't really needed at that point. I had the upper hand and just slowly destroyed Mulcarn's cities one by one. I'm about to get the 3rd piece at this point.

-I found the most useful hero to be Epona. If you head quite far Nor-West with a Scout there is a fortress type thing. Entering the square seems to give you Knowledge of the Ether (I stumbled upon it by chance in my first game using Epona for the tech bonus. It's given me Knowledge of the Ether for every game since).
-Never move units alone. In the beginning game I sent out all my units in pairs.
-Hit Doviello hard and fast. By the time I had Knowledge of the Ether and had a force strong enough (about 2-3 Warriors and Epona the Sorceress) the Barbarian town of Deluoc is big enough to seize. Take it, put a Warrior in there and move on. Harass them with Fireballs until you have maybe 3-4 Warriors and Epona, then soften up the capital and take it (Don't forget to bombard to lower the City Defence). I usually fortify my warriors just outside the city with Epona on the same stack hurling fireballs until it's weak enough.
-At the same time take control of the area just west with the frostling den, send two scouts or warriors. Scouts seem strong enough to take out frostling dens but keep them in pairs.
-Archery. Get it quickly. Archers and Longbowmen are INVALUABLE in this scenario. They make the single best city defenders and are still very strong on the attack. They should be your bread and butter.
-Taking the Doviello capital quickly and keeping it, ensures a Mammoth supply (At least it did for me) a very useful unit later on with 13 Strength.
-To the far west is an Ice Castle thing. Destroy it to stop Frost Giants coming along. I got very lucky taking it out though so not much strategy here but to soften them up with archers and maybe use your hero.
-Assassins don't seem very good at anything other than killing Heros and taking out lone wandering melee units. Which is what they're there for I s'pose.