Lack of progress in upgrading soldiers by battle experience is very noticeable for somebody who came from Native. But as I understand it is intentional and meant to prevent player from raising armies of elite troops. You are forced to play with more balanced armies.
If this is good or bad decision is debatable. Developers did it supposedly to make game more realistic. Problem is, core mechanisms in the game are completely unrealistic and adding unrealistic conditions on to unrealistic mechanic to make it look more realistic doesn't make for a most intuitive game. There comes confusion of the most new players. Realism or not, to make progress in the game requires player to use armies of elites anyway since that's the only way he can consistently beat the opponents of equal or superior size.
The base problem of the realism of the game is, that difference between watchman and huscarl wasn't in the experience, it was for most part, in the social status. You couldn't just run peasant through combat and some training and he became huscarl.
On the other hand peasant who fought in the serious battle or two became much more effective then peasant that did not. Especially first combat does large difference, and this is noted in modern armies too. Game however makes no difference between experienced and inexperienced peasant. Instead, he is supposed to became another troop.
Same problem with other "realistic" design choices of the Viking Conquest. Bows and archery wasn't less effective in the Viking era then in previous or following eras. Bows did not became smaller and arrows more brittle. Archers did not became weaker or blind. People simply did not use bow in combat as much as before and reasons were socioeconomic and cultural, not military ones. Same goes for cavalry. But those are not factored properly in the game. Instead developers decided to make indeed bows smaller and arrows more brittle in order to prevent player from using "unhistorical" tactics and choices. Not surprisingly most new players are left baffled and confused and unless they come to the forum and read lengthily explanation from a developer they probably wont understand game at all and will waste their time trying to play the way which is by design destined to fail, even if it's perfectly logical. They won't even know why thy fail and will eventually probably conclude that the game is bad. Which isn't true.
That said, there are ways around limitations of experience gain. First of all, there is some experience gain in battles and troops will eventually progress, if they survive long enough. Which most of them wont. The thing about MB leveling is, that troops don't gain experience individually, instead they gain experience as a group. This means that if you have large group of one type of troop, one or two of them will be ready for upgrade after one or two good battles. And since higher level troops have higher survivability in combat, you will start slowly accumulate number of high level troops over time. over long time. And you of course can't loose battle. Early game however you run small party and you won't see much effect of this.
So what can you do early game? Forget about leveling your troops through combat or training Native stile right away. Training skill works only on troops lover level then you (or your companions) and troops in VC are much higher level then in native. Training gains some sense only once you reach about level 20. Therefore you have to recruit higher level troops right away instead of getting them by leveling. Leveling simply won't do it. You can recruit good units in taverns as a mercenaries, but those are very expensive and chance is, you won't have money for this.
You can also recruit prisoners. This is by far the most effective way to get high level troops in the VC. Problem is, you have to be able to win battles and capture those troops to begin with, and you need good troops for that. Also recruiting prisoners is more difficult when you are low on level and renown. Therefore this is tactics more suitable for mid to end game.
The best early source of good troops are towns or castles. In towns and castles you can recruit tier 2 troops. These are significant improvement over tier 1 because they come with a shield and some decent 1h weapon, often some javelins. They offer the best performance for the bucks and are enough for most basic early missions.
To recruit from towns and castles, you need permission from a lord, which in turn requires you to have relation 5 or more with him and 150 renown. Both are relatively easy to get.
But the best thing is, that if you then raise your relation with town or castle to 50+, you will gain chance to recruit tier 3 troops from there (only melee ones, no skirmishers). Tier 3 makes for fairly solid main battle line and you can do more difficult missions with them and even fight in a noble wars.
This works also for villages, but you can only recruit tier 1 and tier 2 there (with good relations) and tier 2 will be skirmish line (riders in Frisia). Advantage of the villages is that you don't need permission from a lord, you can just bribe elder instead and you can recruit in the village even if you are at war with the faction.
So my tip for a new player at the start of the game, sandbox especially, is to choose some location, settle there for some time, do missions for two or three local towns and castles and few villages. Improve relations with them, gain renown, do some favors to nobles and gain their permissions. Gain some money. By doing so you will make yourself solid recruitment base were you can go to replenish your armies when you need. Tier 3 in towns/castles and tier 2 in villages is random (once you have high enough relation) but it resets every 24 hours. Therefore if you can't get them right away, give it a try the next day.
