Ooh, thread necromancy, but definitely in a good cause (though not so much recommendations to the OP who has long since moved on I think, but hey, recommendations!)
Anyhow, City of Brass and sequels aren't really SF but are pretty darn good and also scratch the old "hey, why is all fantasy medieval Europe anyhow" itch. Always surprises me that Middle Eastern, particularly Arabic, culture doesn't get mined more for fantasy, especially given the familiarity of Arabian Nights.
On a similar note, if you enjoyed Daevabad, check out Throne of the Crescent Moon by Saladin Ahmed, or for something drawing from similar wells but going in the most completely different direction possible The Golem and the Jinni.