I'm on my first non-tutorial map, and it seems I've made a mistake - I bought the first four (cheapest and weakest) recruiting buildings that popped up, not realizing it would lock me out of all future units. Unfortunately, I've been unable to find a way to remove/demolish buildings in the Stronghold.

Combined with the lack of a save feature (beyond autosave), this is pretty harsh - is there something obvious I'm overlooking, or am I just really screwed for this map?

So, yes indeed. You really are screwed


But fear not, laddie - mercenaries are rushing to the rescue.
They pop up after you build another one of those buildings on the left side of the building screen.
If you don't want to meddle with messy money grubbing mercenaries you could try to use your weak units as they can deal enough damage in the tutorial mission.

Additionally get yourself a new friend, hire yourself an archer hero to go hunt Goblins and other lousy critters.
After a couple of levels he can butcher most enemies without a sweat even before they ever reach him. If you have some weak cannonfodder to squish in between all the better for him.

If that doesn't help as well you can go explore your provinces to get a sorceror's shop.
He sells Gargoyles which are level 2 bastards which are seriously overpowered in the Tutorial mission. Heck they still are overpowered up to Shard N° 4

Hope that helps.

There is another kind of location - a Troll Lair. After clearing it out, you are given a choice of razing it or keeping it and recruiting trolls. Being 3rd tier creatures, such trolls are going to be the only units of this rank easily available for a long time in campaign. They are seriously badass too, give them to a mage who can haste them and no one can stop them.

Harpies are similarly recruited, but they are 2nd rank and I like gargoyles more for this niche.

Yet another option is to try and secure an alliance with one of non-human races. Elves or dwarves are easily the best tier 1 units in the game when ranged troops or heavy infantry is concerned.

Personally I like the Warrior for the tank solution rather than the ranger. With the right equipment and enough levels he can solo pretty much anything in the first 2 tiers without taking a scratch, and with backup even handle stronger critters.

Oh so thats what alliances are for, I just thought it gives you the territory, so I didnt bother and just conquered them.
Also, wiping out a troll lair, yeah, easier said than done! ^^

True, but that's just personal flavor. Most of the time the archer is quicker because he can shot to kill from turn 1, but when surrounded the fighter prevails.
The regeneration bonus of the fighter is very nice. But then again I had a Archer that killed a Troll with a single shot. He was completely overkilling his enemies...
Chose a hero close to your playing style...

Lock you out of future units? I'm noob at this too, so what was built that should not have been built. This game is beating the stew-beans out of me on Beginner! I need some help!

No it only locks you out of the units for that shard you're on. If you restart the shard or move on to another one, the buildings of the stronghold in that particular new shard are reset.