Try to get your Garrison to level 2 at least.
Things you'll want at Garrison 2
1) A reliable stream of Garrison Resources. This is super important. The earlier you get this up and going, the better. Either Trading Post or Lumber Mill. Using your Trading Post costs more in gold, but produces more GR than Lumber Mill (30 to 20).
2) A Salvage yard as one of your small buildings so you can start stockpiling follower upgrades for when they reach 100. Level 2 is needed for follower upgrades so try to rush that.
3) War Mill is a better large building than Barracks when you're leveling. The random upgrades can be really clutch when you're nearing level cap, but it is RNG dependent. Barracks does fuck all, tbh, since your primary cap is GR, not availability of missions. The difference in EXP gain from a patrol mission, which are infrequent, is not good enough to justify it over War Mill. However, it is a decent choice for a second large building. Unfortunately, you're forced to build the barracks first, and you can only get a second large plot at Garrison level 3... So you'll either have to build a War Mill on top of it or rush to Garrison 3, which isn't too difficult if you go treasure/rare hunting.
4) Avoid spending GR on mines unless you really need the ore. The market is oversaturated with ore and it's more efficient to just buy it than farm it yourself. You could upgrade the Herb Garden though, herbs still bring decent money as far as I can tell.
5) Try to level followers as much as possible while you have Salvage 2 yard up. Don't be afraid to have followers go on missions with a <100% success rate. They'll still gain EXP on a failure as long as their level matches the mission level. But don't overdo it either, try to be efficient whenever possible. You want to create a versatile stable of followers, with at least 2 dudes who can handle each mission threat:
Danger Zones
Deadly Minions
Group Damage
Magic Debuff
Massive Strike
Minion Swarms
Powerful Spell
Timed Battle
Wild Aggression
There are also epic followers you can get through cheevos like Croman, Leeroy, and Millhouse who have set base abilities. You might want to factor those into who you choose to level and who you deactivate once you reach your cap (20 followers, 25 followers with Barracks 3 which comes much later).
Some traits (the ones below the abilities) are also really good to have on followers. They are:
Scavenger
Extra Training
Epic Mount
If you're having trouble choosing between one follower and other with identical abilities, prioritize followers with those traits.
Level Epic followers before Rare ones, before Uncommon ones, since it takes a long time to upgrade Rarity (and the number of abilities/traits they have) at 100. Once followers reach Epic level, they don't gain any more exp so exp missions are more or less useless for them. However, grinding missions still generates a lot of salvage and cycles through your list of missions, so it's a good idea to send them on redundant missions sometimes just to get those missions out of the queue.
A good way to "power level" low level followers is to have high level followers go with them on certain missions. For example, you have a 3 follower level 93 mission with Group Damage as the only enemy ability. You have 2 level 93 guys, and 1 level 99 guy with Chain Heal. So you should put the level 99 guy and both level 93 guys, which should bring the mission success up to 100%. This works especially well if your high level guys have the Extra Training trait, and sometimes you'll want to do this even with a <100% success rate.
One last thing. A follower that's 1-2 levels below the mission level (their level on the mission screen will be colored with orange), will only get 50% of all exp. More than 2 levels below the mission level (their level will be colored red) will get 10% of the exp and not contribute their ability whatsoever. Avoid red assignments entirely. Some orange assignments if you're strapped for appropriately leveled missions are okay, but don't make it the norm.
EDIT: Fixed some details.