Compared to R:TW, M:TW has a rather steep learning curve so I would recommend you to start with the vanilla game, as most modifications increase the difficulty even more. Good factions to learn the game with are the Byzantines (rich, strong generals, initially powerfull units), the Spanish (strong units, potential to become very rich, nearby enemy ripe for crusades) and the English (good position, strong units once you hit high), all three in early. If you also got the expansion, you should try the Vikings: they have very powerful units, can loot-and-run with impunity and are generally a very fun faction to play with.

Once you have gotten the hang of the game, I recommend installing MedMod v2.14: it's a balance patch that improves A.I. performance without changing overmuch. If you are looking for something different but still want to stay in the medieval theme, there are three mods available:
  1. VikingHorde's Medieval XL: one of the most popular mods, based on the concept that Land is Power.
  2. Blind King of Bohemia's Supermedieval: a more historically-oriented mod, perhaps slightly less popular but generally held to be just as good as Medieval XL.
  3. WesW's MedMod v3 or v4 beta: the most challenging M:TW mod available, introduced the homelands concept and has the best A.I. performance.

If you want a different setting, you could have a look at Napoleonic:TW, Shogun for M:TW/VI, Hellenic:TW or Pike & Musket: TW.