I'm stuck in a holding pattern on my first shard of the campaign. I'd been through the tutorial a couple of times so I decided to try skilled...but it seems like the tutorial didn't adequately prepare me for a non-sleeping enemy.

I started in a swamp, and maybe would have been better off with a wizard hero, but I took the scout. And maybe given my lack of income, trying to build crossbowmen and swordsmen as my troops was a mistake, but my theory was it would be easier to keep strong troops alive and gaining levels. The first part of the game was a bit of a struggle as exploring my homeland kept revealing giants, battlemages, trolls, etc--stuff I couldn't handle in the early game. But I persevered and took a few more provinces, methodically exploring them, building granaries and pubs everywhere, and mills on the plains.

I hadn't gone far from my home province when I got news that I had an opponent, but I still kept to my creep strategy, trying to build up my strength. Eventually, an enemy hero showed up with a lot of crap troops (militia, slingers, shamans) and I beat him pretty handily and thought things were going well. After this happened a second time, I thought that maybe I'd better try to press my advantage and keep taking his provinces while his hero was dead, so I went on the attack.

Of course, going on the attack means losing troops which meant several turns returning to my stronghold. I built an outpost three provinces from home on my border thinking I could use that...but to add spells and repair equipment, I still needed to go back to the stronghold.

It was only then that I noticed he had two heroes, and realized I could build a second hero, too. At first, I thought I would be able to level my second hero up and use both to attack, but I soon realized that it was hard to find anything he could successfully fight...so he basically became troops and eqipment transport.

And now I just don't know what to do. No matter how many times I win battles against his heroes, they just reappear a few turns later with fully stocked armies again. I don't understand where his income comes from to replenish them because his provinces are mostly unexplored crap. And with two heroes, he can take a province away from me every turn and there's nothing I can do about it. I kill one hero then have to go chasing after the other and by the time I get to him, the first hero is back. And though my troops are always better than his, each battle I lose one or two of them.
And since I'm constantly chasing heroes, I'm not attacking buildings so I'm dependent entirely on my province income, so army replenishment is a problem . I can't see any way to make any headway.

So: where did I go wrong? Should I have gone with cheap troops that were easy to replace? Should I have tried to capture as many provinces as possible so his empire (and apparently income) wouldn't be so much larger than mine? Should I have tried to go after him as soon as I encountered him, rather than trying to build up my strength? Should I have used healers to try and avoid casualties? I found the healer hard to use effectively when I tried it. I still haven't even found his stronghold...

Thanks for the response. I decided to restart and am doing much better by using a healer and cheap barbarian troops, and keeping my main hero attacking buildings almost every turn.