Instant game over with no hint it could happen... Argh.
Back to the drawing board.
ಠ_ಠ

1. Before a province rebells it must be at "upset" for quite a long time. There is a meter on the province and there is an icon in map view that shows up on the province (red frowny mask icon indicate a rebellion is brewing)
2. Province guards would have killed the rebels.
3. Always keep a single unit inside your castle's garrison, then an attacking army (such as rebels) has to beseige the castle first which takes many turns (giving your heroes time to come and kill them).
4. Backup save directory after every shard (in the astral) conquered (number them) so that you can revert to an earlier save.

Provence guards will also slow the rate of unrest (with a couple exceptions that may anger people more like thieves).

and some province guards provide a bonus to population mood... there is even one, dwarves which provides you will extra money if they are placed on a hill with strategic resource.

Two of the guards for forested areas provide mood bonuses and one (the foresters guard I believe) provides a +10% bonus to income. If you have large forested provinces they can be amazing.

1. doesn't seem to be true or it's a bug. I've lost a single player game in less than 20 turns. My province was "Happy". I had no guards. They decided to rebel and I lost. Note also that no other event had happened before this one that might have had them super upset and triggered this rebellion event . Very odd.

Had you made contact with an opponent at the time, by chance? There are certain rituals which cause undead uprisings and the like, which could have done the trick if you had no guards. Invasions from certain neighbouring neutral provinces are also possible, Lands of the Dead being one example that is always risky being next to.

Thanks to the siege trick I've managed to survive and capture a few shards. Then I've attacked a medium shard. By the time I was level 5, enemy's champion beelined straight to my homeland, mutilating everything in his wake. This... did not end well.

I would hardly call it a "trick" to actually have someone stationed in a fort to raise the drawbridge up rather then leaving it completely deserted. true, I think there might be also rabdom events that use the word rebellion (and definitely random events that use other wordings)

Bottom line is, don't leave the castle completely ungaurded when you are explicitly told that losing it = losing the shard.

I always dump whatever militia chaff come with my first hero in the garrison. Saves on upkeep. Helps you remember too since it's once of the first things you do as soon as you arrive on a shard.

Gah. same medium shard, second attempt. Six provinces, scout hero level 5 taking every chance to fight. Enemy warrior at lv 11 just steamrolled everything forever.

I'll try again from scratch some other time.

What difficulty are you on?
Also, taking every chance to fight my first hero is level 25 by the time the enemy's highest levle hero reaches level 11.

Second easiest.

Also, I could fight every turn, yes, but then I'd DIE every other turn because the neutrals were ridiculously stacked, with 14 or so being the absolute minimum for guardians. There's no point fighting if you're going to lose, you know. I actually tried again and got to level 8, before a combo of high level fighter-wizard-commander-wizard-commander within a space of 20 turns killed me off.

Maybe you could record your next game and put it on youtube. Then we can watch and point out what you could do differently. (Or just watch for entertainment purposes.)

I probably shouldn't be one to speak, though, as I haven't tried anything above beginner yet. (I'll try it when I get back to the game -- took a break from Eador to try Zeus.) Maybe that next difficulty level is a bigger step than I'd expect. But at beginner I wasn't too impressed with the strategy AI (and as I understand it, it's the same AI at all difficulty levels, just different nerfs/bonuses). I literally ran circles around the AI -- I captured all of the provinces around one of the weaker enemy heroes and put strong guards in all of them. The hero and his whole army was "stuck", and didn't do anything for the whole rest of the game but repeatedly try to attack my provinces and then retreat before the fighting started. He didn't even explore the province he was stuck in, and just cost the enemy lots of money for troop upkeep. (I kept him in that trap to make it economically harder/impossible for the AI to re-field its other heroes after I killed them -- not because they were really any threat but because their repeated resurrections were annoying.)

I didn't even get to do what I wanted to do that game (get enough building upgrades to squelch all corruption and make a giant prosperous empire) because the population of the enemy's home province started having low morale and I just couldn't resist using a stupid ritual on them that tweaked on their morale even more. Their people rebelled. I saw a catapult sieging its own home province. And then the game was over. Such a sad victory.

Catapult is the image of "non-hero" siege.
Actual army doesn't matter, be it demons or undeads from ritual or 4 militia rebels.