It sounds like Rats and Gargoyles by Mary Gentle, the first book of her White Crow Sequence. It was published in 1990 so it fits the time you remember reading it.
It is a nameless city somewhere between past and future, a mythic realm at the "heart of the world," where wicked Rat Lords have reduced all humankind to slaves, and god-daemons make the decision to end all existence. This energizes a compelling quest for survival, and prompts the powerful White Crow to order an uprising against this chaotic strike that threatens them all. Among those who respond to her are the defiant Prince Lucas of Candover, a student at the University of Crime, and no man's slave; and Zara, the young Katayan woman who is destined to become the living Memory of all that follows. And others rally to join them in one final desperate revolt, hoping to create a magic powerful enough to reshape the very nature of how they live.
We first meet The Hyena in Chapter Three:
A woman in armor shoved herself out of the litter, inch by strenuous inch,
thumping the scabbard of a long sword down on the quayside, and using it as a
"Next person who doesn’t stop I’ll gut. That goes for you, Clovis. What have you found me?"
She stumbled in three great strides to the chair,
sitting with a clash of armor, and waved away all offer of assistance. As she
slumped back into the cushioned chair, two men came to kneel at either side of
"Who-are-you yourself," the woman said laconically. "I’m called The Hyena. I rule the human Imperial dynasty–what there is left of