Oman is in a tough position, with poor settlements all around and no horsearchers (they might get camel archers later on, I'm not sure).

The Abbasids, Ayyubids, and Seljuks are good factions to try first, as are the Ghorids and Eastern Roman Empire. Eventually after playing BC a bit you start to get into a rhythm and even the hard factions become doable.