Probably a good idea to try both christian and muslim factions on early to get used to the different troop types. For your first game you will probably play through high and late anyway, so you will meet most available troops.

For your first catholic game I would go for Spanish. Nice mix of troops, several rebel provinces to take, decent trade prospects and iron to upgrade weapons.

Maybe try Byzantines (orthodox christian) next - awesome mixture of troops and the stongest faction in early, practice managing a large empire and war with more than one nieghbour probably.

Next for the muslims. I love the turks - try them soon, but for the first game I would recommend Egyptians - very strong trading power. This will really give you a taste of warfare in the desert.

That would be my recommendation.