So, I've been recently playing the singleplayer random maps and trying to not suck... but I can't even survive long enough to fight another CPU. No, my problem is that I literally can't even conquer the independent provinces, and I've reset the game many times just trying to get a decent start but just can't.

So, here's more or less what's happening: I start the map, I've tried different starting heroes and army compositions, at first I tried swordsmen and slingers but I discovered that swordsmen are extremely costly to maintain so now I've been experimenting with spearman. But anyway, I spend the first few turns conquering any Free Settlements adjacent to me. But more often than not I end up surrounded by Barbarian Settlements, or Centaurs, or Dwarves, or Elves. And I literally can't take on them with my initial army no matter how I try. And then I end up wasting time and these provinces start getting even stronger. It wasn't uncommon for me to get landlocked surrounded by provinces with garrisons of up to 10-13 units, when I'm barely trying to get by with my Hero that still have 4-5 slots for units available. And even worse is the fact that I still have Rank 1 units, but these monstous provinces with 10 units already have Rank 2 units.

I've already reset the map a lot of times trying to get an optimal start, I even disabled exploration to see how the other CPUs fare in comparison to me, and obviously they're much better. When I'm trying to just consolidate power in conquering the provinces adjcante to my capital, the CPU is already conquering the adjacent provinces to the adjacent provinces to their capitals.

TL;DR I suck, please help me.

Swordsmen are expensive because they are very strong. Swordsmen + healer is a very good combo.

I usually start with a scout as first hero. He will kill the enemies while the swordsmen protect him. Give him some spells to hurt enemies that are resistant to ranged attacks (like skeletons, dwarves or ghosts) Web can be useful too.
My second hero will usually be a wizard.

When I play Good I always pick swordsmen, crossbowmen (for decent early guard units) and healers.
Second tier units will be monks and guards and usually baslista.

Some races can be befriended and will allow you to recruit them if you preform their quest and construct their buildings.
Good races: Elves, Dwarves, Halflings
Neutral races: Centaurs, Lizardmen
Evil Races: Orcs, Goblins

Hey! I see you're new to tile strategies. That's not a bad thing, these are some of the most fun games imo.

So your biggest problem is getting started in a shard. You're obviously fighting neutral territories. First, lower the difficulty! The stats of the neutral inhabitants are dependent on your difficulty setting.
Now you need to take note of the types of units fighting each other. There are three types of damage; melee, ranged, and magic. There are three types of corresponding defense to go along with these. Terrain has mild effects of increasing the firing range and melee damage, forests increase ranged defense, and swamps decrease melee defense. So put your units on terrain that helps when fighting.
In general the units are kind of rock-paper-scissors. Warrior types beat archers who beat mages. The warriors have enough armor to absorb arrows but quickly fall to magic. The mages have a terrible time with arrows. Warrior types like swordsmen are an easy early unit to use, just avoid spellcasters. Shifty units like halflings and goblins will try to beat you through draining stamina or using poison.
If you want to start with the most balanced and cost effective units, then use spearmen. These units can resist some damage, maneuver, and have decent ranged and melee attacks. Sometimes the tavern will toss you a nice unit to break up the early hexes but these units cost double the maintenance. You really don't have economy to waist turns refilling health on tavern hires, so either hire units that can heal or get spells and rituals to keep them fighting and earning you money.
The mage is the hardest hero to start with. He will be useless without crystals even if you are good.

I had to save scum and time reverse a game where my warrior was powerfull enough to take on any unit at level 23 with best armor i could get and a weapon that does first strike with poison ability by my warrior and the use of some magic.
But then i was suddenly surprised by the enemy summoning a vampire while i played a campaign shard too long don't even have all the T2 units since that was my 9th shard and met the first necromancer master on the shard where i was trying to get T2 unit buildings. The vampire and others killed my warrior, that scout summoned a vampire somehow in battle.
It took several retries but i was capable to beat the 9th shard by simply going back to my save with a level 16 warrior and just go through the easier route of enemies and rush their castle.
And lol what a difference one terrain made, being on a hill made it easy to beat orcs and goblings vs on a tree tile and
close to swamps was a death sentence to my warrior on the same map, while the warrior complained he would get trampled on both of those maps.
For starters what i do i tried getting the guards guard in the campaign and when you start it's good to check out search the provinces and enter different buildings for rewards and xp farming which if you can beat them to level up. Equip your hero with armor and weapons when you can and i used storehouses to fix his equipment on the way sometimes i even needed to change a weapon in battle. Even building that fort or something on the way to have closer unit access but it was usually just my warrior who did all the work by himself
Also i lowered the difficulty to skilled for now.

So main thing to do first search the provinces in your homeland and get exp by going into buidlings you can manage to defeat enemies for your heroes equip them with weapons armor accesories.
Get some guards on some provinces where the enemy is close, you would need to know which buildings give which guards.
The problem is i only played mostly with warrior hero at start for now.
Maybe use spearmen for the starter units or what ever is close to your financial situation and resources.
I did use spearmen swordsmen healer and crossbowmen for start.