Hi Rostam! Welcome; we're glad to have you on board (along with your questions)! I'll answer these more or less briefly, which will probably either leave you with questions or give you more, so feel free to ask them too!
Is this a region of city-states, loosely ruled by a single figure, or is it more cohesive?
The Sirdabi Caliphate is more cohesive than that. The caliph is at the top, as the temporal ruler and spiritual successor to the Prophet al-Azad. Beneath him the caliphate is broken up into provinces, each ruled by a provincial governer called a bey. Each bey is appointed by the caliph himself, but the province in question may or may not have some input into the candidate. A well-behaved province may have the opportunity to submit a slate of candidates whom they deem desirable, and the caliph and his advisors will vet the candidates and select one. More typically, the caliph will simply appoint someone he deems suitable, local or not. In the traditional case of Raziya, the bey is a member of the caliph's family. Troublesome Tessere recently saw its locally-chosen bey die under suspicious circumstances, and his successor was an outside appointment by the caliph. There is a fair amount of centralization, with taxes and other goods flowing partially to the capital, but at the same time provincial beys and their courts have a significant amount of leeway. Tax assessors are typically appointed by the provinicial bey, so there is ample opportunity even to siphon off some revenues that might have gone to the caliphal government. There are a lot of cracks in the system, and of course the distances are large, and even with an extremely efficient postal and courier system the caliphal court can lose sight of things happening far afield in the caliphate and find itself behind the course of events. There is a strong feeling that all Azadi are part of a broad cohesive spiritual community, but in matters of self-governance opinions differ -- some people would love nothing more to achieve independence, while others prefer to remain under the admittedly fairly dazzling and prosperous aegis of the caliphate.
What part do the militaries play in politics? Are there mercenary companies wandering around like Renaissance Italy?
The military as a whole doesn't tend to play too much of a part in the politics of the caliphate, currently. The Lion Guard, the standing army of the caliphate, is presently rather weak, having had a lot of its revenue siphoned off during the last hundred years or so of relative peace. There also have been troubles with ambitious and meddlesome military men in the past, which may be another reason why the size of the Guard has been allowed to diminish along with the threats from beyond the borders. Overall, the caliphate presently has a strong civil government and threats from within the military have tended to vanish with mysterious convenience. On the other hand, the caliphate has begun to see an increase in troubles along its borders, and the Lion Guard is starting to prove inadequate. More mercenaries have been hired to deal with hot spots, and the caliphate has also come to rely heavily on non-military measures to resolve difficulties, namely spying and assassination, though sometimes just extremely wily diplomacy has served well too.
Can our characters start out as Caliphate agents? Military, Tax Administration, Ministry of Information, Ministry of Scales, things like that?
A character could definitely start out filling some relatively minor role in the caliphal administration or military. I probably wouldn't have anyone start off with a particularly prestigious, unique post, but having middling to lower-ranking roles within any of the bureacratic or military apparatus would generally be fine, and excellent fodder for telling stories!