Most of the time I started playing as a count, and I agree that for Christian counts the first thing you can do is to hope that the fabrication of county claims went quickly enough. For the army, I suggest you go into full tyrant mode by banishing your mayor and bishop, which also gives you temporary income bonus and a title to give to future county claimant once you become a duke.
In my latest game I started as the count of Mali (Farin Lahilatoul of House Keita). A muslim count is slightly easier to play thanks to the conquest CB once you get enough piety. However, the tricky part is that whether you decided to form the Kingdom of Mali or not; you know those occasions when Mauretania blobbed right? Forming Kingdom of Mali will put me in an eventual losing war with the Almoravids and will severely hinder my World Conquest plan.
So what I did is that I swear fealthy to Mauretania once I gained independence, then proceed to dynasty-purge the Almoravids. With 7 counties and a duke of Songhay title (the duchy of Mali is taken by the sultan and he gives it to his son

, but I'm doing a dynasty purge after all so sooner or later I can create another duchy), I am in a very good position to inherit the kingdom of Mauretania once the dynasty-purge is complete. And how I collect enough people who hate the sultan?
I summarize my plan into these steps:
- Invite a few holy men / nobles
- Find some infidel girls with zealous trait & high intrigue. If they're lowborn / their parents are not ruling somewhere it's a plus
- Marry those girls to one of your new courtier, possibly the courtier with low intrigue score
- After all those girls arrive at your court, kill the male courtier
- Paddle those girls to the sultan's court through marriage. They will hate the sultan enough & willing to plot for free / some golds
- Rinse & repeat until you reach desired plot level
After ~10 Almoravid males and ~6 males from the duke of Tangiers (who inherited the sultanate first), eventually it's my turn to become the Sultan of Mauretania. Then I proceed to banish the last 4 maghreb count and replace them with my own Mande count. Sadly I have to culture shift my dynasty & those counts to Catalan due to my dream of becoming an emperor (and I did become one on my third character).
Be careful though, those high-intrigue girls can also kill you. My first character died in a manure explosion...