The Court of the Malik
The characters will eventually wish to meet with the Malik, perhaps to deal with him in order to rescue King Kush. If they also are seeking to rescue someone that was captured by an 'afrit after opening a Brass Bottle, then that individual has been sold as a slave to serve the Malik's court.
Gaining access to the Malik's court is much easier than the characters might expect. The palace, like the other buildings of the city, is actually a Vestige, and has many open doorways and windows that make it easy to enter or pass through. Still, it may be the instinct of the characters to come up with a clever ruse or means of infiltration. Whatever their method of entrance, the Malik plays along, making it seem much too easy. If the characters pick a fight with some of his guards, all the better! The characters can also simply walk into the court and stand along the outer edge. No one stops them, but it may be difficult to get the Malik's attention.
The Malik's court is crowded day and night with throngs of jinn seeking the king's attention. Some courtiers come merely to participate in the constant feasting and drinking. The Malik sits upon his throne of red carnelian, with a score of honored guests sitting along either side of him: nobles, dignitaries, diplomats, and other elite. The sarcophagus of King Kush stands behind him, the monarch's spirit bound as a hostage to the red carnelian throne. The center of the room is kept clear for summoned speakers and the various entertainers performing in court that day.
The constant circus of the Malik's court continues without end, but occasionally the Malik is absent from court when he chooses to take rest. Every seven days or so, the Daimon discards the Malik Aspect, and reappears a day or two latter upon his throne of red carnelian.
Gaining an Audience
Along the outer walls stand the common masses, all seeking but a moment of the Malik's time. Though the Malik may seem frivolous and jovial, he is easily offended and has a fierce temper. He calls upon those seeking audience as it pleases him, and it can take hours, days, or years of constantly mingling in court to receive his call.

One way to get the Malik's attention is to pay one of the courtiers to address the Malik on the characters' behalf. Another method is to organize an entertainment, and give a message alongside the performers. The Malik's greatest vice is that he desires constant entertainment, so even a speaker with an important message may have to compete with a musician and a juggler.
The characters may struggle to get the Malik's attention, but he has been aware of them all along and is just playing with them. As unknown quantities, they are a new distraction that the Malik hopes will prove entertaining, in whatever form it takes. When the time is right, he drops the pretense and invites them to sit by his side at court as honored guests.