Hard to say what you are doing "wrong". I'm definitely a cautious player myself, and a lot of what you say you do is my playstyle as well, but for me Skilled fits just now, so there must be some differences. I've started Shards with Warriors, Wizards and Scouts without any noticable difference in difficulty. The Warrior is slightly easier - mostly because he can use almost any gear you find (all kinds of armor) so he gets strong faster.

Perhaps you are even more cautious than me? While I play slow and develop a lot of my lands as well as search a lot of places, I do not go all out on this. I always prioritize getting a new province over searching a location if I have the army for it - searching locations is for when you are recovering, need to build up some gold (especially early on) or secondary heroes...

hmm i consider myself cautious as well and what i do nowadays (on beginner i have to say - i am not hard enough for a more difficult game) i use a warrior as first hero with three bowman and he can normally conquer all six neighboring provinces without loses unless they are hardly guarded (holy lands- nomad tribes - and sometimes barbarian tribes with 3 barbs and one shaman are hard early on) - after that i try to clear the locations in my home provinces to get some gold so i can buy a second hero and the theater - with that a pub can clear most cases of unrest and is rather cost effective

Warrior to start, then Scout to mop up everything else I guess ^_^

And yeah I am pretty cautious - hardly doing much early game. I think I spend too much time exploring and not enough time expanding D=

I only scout if there is nothing else to do (like conquering, fighting dungeons or buying new units, repairing gear) or if the province is not orc/goblin and can´t grow otherwise.
It just doesn´t seem to be worth the timeinvestment with the first hero since you often find nothing or dungeons that are to hard.