Playing Two Continent, Four Players XL
When you go to the second continent, there is couple independent armies where it says "Legion"
I've left them alone
But I had a high level Captain with high diplomacy, so I attacked a Legion of Pegusi.

A Legion is 4000. LOL. I can't even afford to upgrade them.
But at least I know what a Legion is now. But it also makes the game feel pointless now.
Edit
I've leave = I've left

Were you able to recruit them?

Yep

Does HoMM 3 use the same scale as HoMM 2?

Few = 1 - 4
Several = 5 - 9
Pack = 10 - 19
Lots = 20 - 49
Horde = 50 - 99
Throng = 100 - 249
Swarm = 250 - 499
Zounds = 500 - 999
Legion = 1000 plus

HoMM 2 has a map, in bad guy Archibald's campaign, with a legion of peasants to be fought and killed. It has also a special character hero, Lord Corlagon, who despite being a knight knows necromancy, the skill of converting slain enemies into skeletons for his army!

Sounds right.

You're rocking the Sword of Judgement, Tome of Earth Magic, and Angel Wings, among other powerful artifacts, with 19 Archangels and 31 Ancient Behemoths, and you're concerned about 4000 pegasi breaking things? :D

Throw the pegasi in a town somewhere; they're slowing you down until you can upgrade them. Toss out the Zealots, Grand Elves, and especially the Diamond Golems(!) too. The Royal Griffins aren't impressive either, but at least they aren't slowing you down while you're keeping the Ancient Behemoths.

Have you tried the Dragon Slayer AB campaign? I enjoyed that one, and it had some ridiculous battles too. I remember that map. I thought "meh, peasants are easy!" and went after them with my one bone dragon. That was a swift lesson in how numbers have a power of their own.

The Diamond Golems are still slowing you down; I'm not sure 45 of them are worth slowing overland map progress turn after turn. The Zealots aren't bad, but only 20 Grand Elves probably isn't worth a creature slot when you've got Expert Diplomacy. Lack of Air Magic and Earth Magic is also sad. :( Did you avoid them?

Anyway, I am intrigued. Is that map formally named "Tale of Two Lands"? I hope so, since that's what I just started. If it is, I haven't seen the behemoth crags yet, but I have seen 3 Fire Elemental Confluxes, and they've been a big help thus far. I probably should have devoted more of these numerous chests to gold instead of experience and I might have a Capital and Portal of Glory already. Oh well.

That's the map. The Caves are closer to a second castle that I usually go for. I build up two heroes. One I keep toward the middle of the Continent to keep bad guys off my home turf. I give him the Fire elements (upgraded) as his go to fighter. Three fire caves can give you quite a few.
The second hero, I build around the second castle. An army of whatever and the behemoths. Upgraded they can take a lot of damage.
I like that map at harder levels. And still lose more than win.

Neat. I'm trying it at Hard difficulty, so I'm probably going to win. I started with Red and I've broken out of the lava area, but I haven't seen a second town yet.

Also, I apologize for jumping straight into critiquing/suggesting, though. You already know what you're doing.

No problem at all. Kick butt!

I'm on it! Also, I just found two Behemoth Crags and cleared them. Now I just need more money to afford Angels, Behemoths, and upgrades for them.

I've taken a Conflux town, I've found the Tome of Fire Magic, and Dessa has appeared in a Tavern to become a second adventuring hero. This game is already as good as done, especially if I can find the Grail first.

(I've found a Necromancer town, but haven't managed to take it yet. Big whoop when I can already use Castle and Conflux troops.)

Sounds like a good game. Conflux are weird towns but the Aurora is neat

Finished it out pretty easily. I found the parts for the Wizard's Well combo artifact (full mp restored each turn), and I finally dug up the grail. The AI just can't cope with a stack of Phoenixes backed by all spells at Expert. Aurora OP!

I wonder which town type is the weakest on this map. Fortress maybe, since they are low magic, their creatures are slower and rely on tricks, and they don't have much in the way of matching creature generators on the map.