Family wealth might also have something to do with it, as well as fame. I know if you have a certain amount of wealth you can choose to recruit larger numbers of soldiers first starting out than you would ordinarily get. Presumably, it's also a bit more expensive to start out with Cavalry than it is with Infantry or Archers.
