Mount And Blade: Warband
- If you're looking for something to do in the early game, the best options are the guild masters in every major town (use the 'take a walk around the streets' option or whatever to find them), who are guaranteed to have jobs that often pay well, or you can go to a tavern and ask about jobs, which will let you know about any particularly high-paying ones.
- You will also definitely want to improve your relations with villages by doing quests for them, since that makes them offer you vastly more units, and higher-level units; recruiting a mass of 20+ guys from one town that you're in good standing with is much less tedious than roaming around getting 4-5 from each village.
- Once you have some money and a decent army, you'll want to ask lords for tasks until you get offered a mercenary contract, which will let you fight in that kingdom's wars without standings repercussions (your standings will reset to neutral after the war ends, although if you loot/burn villages they'll hate you forever, so avoid doing that for the aforementioned recruitment reasons.)
- Once you've spent a while as a mercenary/vassal you can fight for a pretender or start your own kingdom.
- Horses in M&B are insanely strong and you can easily kill 30+ guys per battle mounted, but personally I think infantry gameplay is more tactical and fun, so try them both.
- The nords and rhodoks are definitely an extra challenge, so the vaegirs might be a good choice if you're looking for a balance, since you have strong on-foot options but can still go to town with the horses when need be.
- Don't worry too much about your character, though, since skill points don't make a big difference and any character can be an all-arounder.
- If you don't mind being obligated to keep party members around, you can skill them up in stuff like wound treatment and save your stats for charisma and combat. It's also fine to spec in that stuff yourself though since going around without wound treatment for even a little while can be brutal.
- Acquire Nord infantry in as large amounts as you can get them. Their final evolution, the Huscarl, is probably pound-for-pound the best unit in the game. They make sieges (both defending and attacking) so laughably easy that I've had to restrict my usage of them just to inject a bit of challenge.
As for bandits, just keep clear of the northern coastline until you're confident you've got a reasonable force. Sea Raiders are your worst enemy on in game; stick to fighting nice nice soft forest bandits.
The various kingdoms each have their own playstyle and I highly recommend you join the kingdom that suits what you want to do. In order loosely from strongest to weakest:
Khergits: Horse archers and lancers with no regular foot units, the easiest faction for a beginner
Swadians: All-arounders with a focus on lancers, also very powerful
Vaegirs: Archers primarily and cavalry secondarily, their infantry are not so great
Sarranid: General all-arounders with no real focus
Rhodoks: Spearmen primarily and crossbows secondarily with no cavalry at all. Presumably strong against horses but the AI aren't that great with spears.
Nords: Infantry only with axes and bows, often gets massacred by horse-heavy armies.