Hiyas all.
I used to obsess over HOMM 1 and 2 when they first came out, and now I bought HOMM3. Been working my way back to however good I'm going to get at it.
I am playing "hard" now, and do very well on maps up to the "large" size. Now I've started on the extra large size, and it has thrown me for a loop. I've even abandoned a couple of games out of frustration.
What happens is, I'm keeping busy, but after a while my level 24 or whatever bumps into an enemy who fearlessly challenges me -- and when I see his stats, I see why. I can't make a dent on him and he eats me up 30 dragons at a time because he has attack and defense almost in the 40's. I simply can't seem to get through the map that fast without losing so many soldiers that I'd just start to slow down again because of lack of soldiers and/or lack of money limiting my expansion.
Anyway, anybody got any general tips for playing on extra large maps? Or any other sizes, for that matter. PS I'm now playing with that what's his face side, umm...the one with evil eyes, medusa queens, minotaurs, scorpicores, and black dragons. Doing well too, until I started on extra large maps.

It's quite difficult to answer that kind of question. I don't know what kind of answers you expect but I can try and provide you a few advices. Or at least tell you a few things about the way I manage my XL maps. Since you were obsessed with HoMM1 and 2, you may already know some (if not most) of what I'll tell you though.
The fact that most of the time you run into fearsome encounters with stats far higher than yours, makes me think that you waste way too much time at the beginning of your game.
Exploration and buildings selection :
Needless to say that you have to explore as fast as you can the surroundings of your town to grab your ore pit and sawmill. The construction schedule is not hard to figure out, but most of the time, I tend to get my level 1 and 2 units (my selection can be different depending on which town I decide to start with, of course) and then rush for the capitol. If you are running short on money (and besides archers) do not upgrade your creatures unless it's an absolute necessity, save your money until you have a clearer view of the situation.
Speaking of that, and depending on the nature of the terrain (if you have lots of open spaces for instance), don't hesitate to buy one or even two extra heroes that you will use for exploration purposes only. Most of the time, you should be able to judge whether you need them or not during the first week. Again, don't waste your time making that decision. Use those heroes to grab every "free" resources from the windmill or that you may find on the map, collect gold from the watermill, check the shrines of magic (don't neglect those, you'll be happy to know where you can get "slow" or "haste" if your mage guild level 1 doesn't provide them) and do not neglect scrolls (those can make good toilet paper).
Main hero :
I usually start with upgraded shooters and fast creatures. That combo works pretty well for me. I choose to fight the slowest enemies (zombies, skeletons, gnolls, whatever low level you find). I use my fastest units to lure the enemy (try to use the reliefs of the battlefield) while I shoot them with my archers. If you manage that well, you will be able to kill good amount of monsters without any casualties. Easy experience.
Do not neglect free bonuses such as "star axis", "learning stone", "mercenary camp" etc.
As you found out, those stats are way too important to be neglected. Unless you have lots of gold, and unless those are far away from your town, avoid the bonuses that require you to pay. Save those for when you will be financially stable. On the other hand, for treasure chests, I always pick up experience instead of money. But again, that's a personal choice.
You have mentioned playing Dungeon (my favorite town) and I say that it's a good choice for a start. With 2 archer creatures (fairly easy to get) + the harpy hags (who behave like archer when you think of it) that should be easy to get started.
This is a non-exhaustive list, I probably forgot dozens of things and I could add more tricks (more or less important) but I'll stop here. I hope this helps a little bit. Not to mention that it also depends on how you manage your fights. That is a very important factor as well...

Thanks for the feedback so far.
I too tend to concentrate on archer characters so I lose very few soldiers. I will concentrate on getting the town hall, and try to get my shooter recruitment buildings in the first week if I can, so that I am increasing their number right away. I often put off upgrading my troops for a long time, until I get my money-generating buildings, except for archers.
I fill in my melee characters much more slowly, and may have a lot of them sitting waiting in their buildings before I upgrade their buildings or buy a single one. If archers are doing the work, I figure I'd better get a capitol first.
I also never know what I am going to find while looking about, but try to get another town ASAP. If I do, I will build up its money-generating buildings immediately but ignore its creature buildings. My first goal is to build up enough money to fully equip one rock-solid hero with plenty of troops. I find you can't buy all the troops from one town unless you have at least one extra town you use only for money and don't buy soldiers from, or have some extra gold mines.
But I still find it bizarre that I keep bumping into guys who have twice my attack and defense. What the heck are they doing? For instance, I bought a map from a cartographer so i could see all the upper level of an XL map. I saw all of two castles upstairs. Meanwhile I have two downstairs and two upstairs. Sounds about even, right? I bump into him and he I have about 25 offense and defense and he has about 50. 50!!! Where the hell do you get that kind of stats from? My hero has hit everything on the map, even used dimension door to get around, and been fighting non-stop, getting fed new soldiers constantly from two of the same kind of town, a non-stop orgy of destruction. I met his characters twice on the battlefield and beat them till they fled.
I'm getting pretty frustrated.
One thing I noticed is that I have expert logistics, but the enemy's main character is covering gigantic amounts of ground and fighting an amazing number of monsters in his turn. This makes me wonder if I should do everything possible to get both pathfinding and logistics. (Didn't have the opportunity this time.)

Those high stats could be from map objects like star axis (as Cambrey has already said), also by leveling (high level hero = higher stats), visiting 4 certain buildings from 4 towns (stronghold - hall of valhalla: +1 attack, fortress - cage of warlords: +1 defense, inferno - order of fire: +1 spell power and tower - wall of knowledge: +1 knowledge), visiting library of heavenly enlightment (after lvl 9 or 10 you can visit it for +2 to all stats) and of course, plenty of artifacts (some add to all stats, some add a nice bonus to one stat). That AI hero could have visited all possible places he encountered, and on a XL map there can be plenty of them.
To movement: pathfinding only helps on harder terrain, like rough, snow, lava, swamp, etc. If the map consists most of grass and/or dirt, pathfinding would be a waste of a skill slot.
Some heroes have logistics specialisation (=even more movement), like ranger Kyrre, and 2 or 3 artefacts increase movement on adventure map (like Equestrian's Gloves).

Because my dungeon or whatever guy starts always underground, his passage over terrain is almost always rough (sand) and his passage between places can be slow (the underground has much more restricted movement in the narrow channels and paths IMO). He is also more likely to be blocked up at a chokepoint it takes some seriously troops to get past in the early game.
But even given the best of all worlds where untoward things don't happen, I am confused how a guy can have twice my stats at level 30. This guy has been fighting non-stop.
Maybe I need to get him exploring more and fighting less? I'v'e been doing that lately -- he has been leaving many fights behind for some other time or for a secondary hero once he gets strong enough -- but still I guess it's not enough.
I am thinking of making my next map no underground so i don't start at what feels for me like an initial strong movement disadvantage.

Maybe he has visited some trees of wisdom (or whatever are they called. I mean those which give you level up when you visit them).
However if that player's position isn't AI only (=you can select his colour at the start of the map), start a hotseat and try loading your saved game. If that colour isn't only for AI, you can select his colour with one of the players and then inspect his hero(es). I know this worked in vanilla H3, hope it wasn't just a bug which was removed in latter patches.

Sometimes they rush for "dragon utopia" that provide major artifacts. Try to empty one of those as soon as you can.

Interesting idea, I may try that. I wonder if he has got another six castles somewhere, or something.
This map is interesting. I'm used to every terrain type you transition into having at least one castle. I've bumped into at least one this game that doesn't have a castle on it at all. That wasn't a complete waste of time, but a castle to seize would have been nice.

A couple days later, now the journey continues.
My new strat was to back up a few weeks and get far away from enemy territory with my main hero and all others. I was able to get better scores on attack and defense by hitting a library and going up a few levels. But then I got hit by the enemy.
He charged me even though I had a massive troop advantage. However, when I looked at my attack/defense, it was something like 34/34, and his was something like 34(59)/33(58). Holy cow. My guys hardly made a dent in any of his stacks, and his decimated mine in one or two blows. I was about to abandon the game, but unfortunately you can't quit out of battles if you don't have the money and/or the enemy has the shackles artifact. So I hit autoplay -- and won the battle.
My automated side kept casting earth elementals. The enemy's stack of 50 titans would charge after it preferentially and get through it in one to two blows. But by that time, the blind spell would be one or two turns closer to wearing off.
And yes, he even blinded my magic immune black dragons. And yes, since they are immune to spells, I could not cure them! WTF!
At any rate, most of my army died, but since I had about 1100 mana and could keep casting earth elementals like mad, I did have some that survived. When I won, I got an incredible flood of artifacts. But more importantly, since I already had so many artifacts that even some of my lower heroes got some good ones, this guy had tremendous artifacts, like one after the other that gave stats like +4 to +5 to all stats. That made each artifact add about 20 in total to stats. My previous outfit enabled me to put together the Titan's thunder sword, but it had +12 to one stat and -3 to another on I think two or three pieces and +10 to one stat and -2 on another. So my pieces -- and these were the best pieces I've ever gotten in the game -- were averaging out to about 9 stat points each, while he was wearing stuff that averaged out to mostly 20 points each and I guess one was 16 points. No wonder he was kicking the crap out of my army with a much inferior one.
My problem wasn't a lack of items. And I had gone through half a dozen dragon utopias before this final meeting, and hunted up items all over the place. It was that my items, though fanastic, weren't even close to how fantastic his were.
Apparently there's a strong luck of the draw here. The only way I finally beat this guy is through not just overwhelming force of numbers, but overwhelming amount of mana. And the overwhelming tendency of the computer to keep chasing down my earth elementals instead of finishing off the last few remnants of my army. Thank goodness for small favors.
... and now the journey continues. I have great stats, but a decimated army, and the enemy still has heroes roaming around that have untouched and at this point untouchable massive armies ...

Heh, the Orb of Vulnerability; I love that artifact. By the way, out of curiosity what's the name of the map you're playing?

It's a randomly generated map.
I didn't even notice that I got that artifact and hadn't known it existed. I'd thought that was just a bug. Hmmm now I gotta go look for it!
Lemme tell ya, when you're fighting more than 50 titans at a time, the last thing you need is your dragons disabled. These fights have been every kind of nightmare rolled into one.

Blarg it sounds like your playing a Magic caster hero, so if the enemy is the warrior type hes going to get better attack and defence stats just from leveling up.
Also a fantastic trick which will even up the game alot more is have a resource gathering hero following your main hero about. What this allows is your main hero to only concerntrate on battle and picking up experiance chests and things he needs. Then all the extra resources that go into your town you pickup with the crappy hero that follows him about. Over the course of a xl map game this will make a huge difference in what you are able to get done. You don't nessacarily need the resource gatherer at the very beginning depending on the map but once you start moving out of your initial area its well worth the gold.

That's a good point too. Your opponent had about 25 points on you, but about 10 each of those were from artifacts, I can see at least a chunk of the remaining 30 (15/15) coming from being a Warrior class. The rest? Not sure.

It should prove quite useful to you, as with it you'll be able to now hit titans with either Blind or Forgetfulness (as they're normally immune to mind spells). Also, if you're playing a hero that has a large mana pool then Blind + expert level Resurrect is a great way to avoid losses in battle. Just blind your enemy's last stack, then resurrect to your heart's content. It might take a little while and be a bit of a cheesy tactic, but you can't argue with its effectiveness.

Yes, luck is big factor in Heroes games. You can be better player than the other one, but if he gets more luck/morale procs, you're pretty much screwed, not to mention luck while finding artifacts.
Of course, you're right. Even hero type (caster/fighter) can make big difference. The biggest fun is having might hero and then find artifacts like Orb of Inhibition, which will render caster heroes (and their superior DD spells and/or buffs) useless. Then you can kill his units without problems.
However IIRC there is a attack/defense bonus cap, so against enemy with quite low defense skill your ultra high attack skill could make no big difference if your attack was lower. I know that Heroes 2 had no such cap.