Well, if you start as a Nord, you don't start mounted I believe. They have no cavalry by default; while you can train your own riding skill and purchase one, i don't think you'll start with one.
Swadia and Rhodok are probably the easiest starts, Nord, Khergit and Sarranid the hardest. This is because:
Rhodoks have easily defensible terrain, well suited to bows and crossbows.
Swadia has generally flat terrain, but their bandits hang around forests and are generally easy to fight.
Nord: They have the rather strong Sea Raiders as their local bandits. Nasty for an early game player, they hit VERY VERY hard.
Khergit: you like bandits? now have bandits on horses with high Horse Archery. If you're light on cavalry, you're screwed.
Sarranid: Desert bandits seem to clump in rather large numbers. Also, the terrain is flat.
No, you start mounted no matter what. Technically speaking, you don't start as a Nord, you start as a traveler in a town of your choice.
Also, Nord is probably one of the easier starts, and Swadia a harder one. Sea Raiders don't raid Nord mainlands, they stick to pillaging Rivacheg and thereabouts, and Nords are some of the best troops in the game (Huscarls cut through the enemy like butter and Nord Veteran Archers are some of the best bowmen in the game.) Swadia is hard because they're in the middle of the map and generally die fast, sometimes becoming irrecoverably weak by the point you're strong enough to become a vassal or make a meaningful contribution with mercenary work.
The troop lineup by faction is something like:
Nord: Excellent infantry, great archers, no cavalry. Excellent at assaults and good at field battles. Top tier units are Huscarls and Veteran Archers.
Vaegir: Good infantry, great archers, great cavalry. All-rounder, but somewhat weak defense due to lack of shields. Top tier units are Guards, Marksmen, and Knights.
Swadia: Good infantry, good crossbowmen, excellent cavalry. Dominate field battles, good at sieges, but troops are expensive. Top tier units are Sergeants, Sharpshooters, and Knights.
Rhodoks: Great infantry, excellent crossbowmen, no cavalry. Siege warfare kings and masters of defense, but bad at offense. Top tier units are Sergeants and Sharpshooters.
Khergit: No infantry, horse archers. Second to none in the field, but get murdered in sieges and hilly terrain. Top tier units are Lancers and Veteran Horse Archers.
Sarranids: Bad infantry, great archers, excellent cavalry. Better than Swads, but only if your troops are high tier and low on infantry, because their armor sucks at low levels. Top tier units are Mamlukes, Veteran Archers, and Guards.
Rhodoks and Nords fill a similar niche, but require considerably different gameplay. Nords are super strong overall, and you can just tell them to charge when the time comes; the archers can also hold their own as medium infantry. Rhodoks require defensive gameplay where you have the infantry guard the sharpshooters, then charge when the enemy closes in.
Vaegirs are basically budget Swadian troops. Prioritize cavalry but don't slack on infantry and ranged support.
Khergits are best as field troops. If you go Khergit, consider importing Rhodok or Nord troops to man your castles and help in sieges.
Sarranids have horrible infantry but god tier archers and cavalry. Definitely go for quality over quantity with them.
There's also non-faction troops promoted from farmers and peasant women (they can be rescued from bandits and the males can be hired in taverns.) The "mercenary" troops (swordsmen, cavalry, crossbowmen, and Hired Blades) are strong but expensive. Sword Sisters are very strong, but they need considerable support from fellow cavalry due to their low hit points and weak horses; hold off on promoting them until you have several ready, because they ride the fastest horses in the game and will outspeed your other cavalry unless the enemy is very close. Consider using these units if your army lacks or is weak in a unit type (such as cavalry or strong infantry) and it feels wrong to import troops. Low-tier mercs also make nice castle guards.
Don't try to bother with captured bandits, they suck in more ways than one.