Here’s what I did to romance Iskander. Not entirely sure which parts are entirely necessary, but this worked for me.
When you get the chance to go see Iskander after getting a djinn, take it. When it asks how you feel about Iskander sleeping with someone else, say you don’t like it and confirm you have feelings for him. Take every opportunity to work with Parveen that you can. When Parveen marches on the palace, help her goad Yusr and have it end in a riot. Don’t try to mediate between the two, Parveen will see that as you betraying her and that will cut off further work with her. The next day, go help spring Iskander from prison, and you should get the opportunity to hang out with him afterwards. This will let you confess how you feel and start a romance with him.