I read this novel in either the late 90s or early 2000s. The setting was fairly low magic, but events in the novel signaled that magic was returning in a stronger form.
Parts of the setting/novel I remember:
Fala was a fire goddess and seemed to have been incarnated in the form of a woman that caused fertility-related maladies in men. Priapism in one, who became obsessed with finding her, and impotence in the one who traveled with her.
A sea god named Sur
There was an unflattering, middle-eastern coded civilization, where the women were forced to wear veils that only exposed their mouths. One character was an abusive sadist, and his daughter (a princess?) regularly rebelled against her culture.
There was a pair of royal brothers. One was virtuous, the other was evil and ended up an obese invalid after an injury caused a coma, and his mother over-fed him while he recovered.
There was a woman who was either a mercenary or guardswoman. She had a lover- a traveling man with a tattooed body. There was a scene in the novel where she read his tattoos by candlelight, and he became distraught because they were magical and seemed to foretell some sort of disaster now.
At one point, a girl tries to bleach her hair blonde to impress a visiting man of some sort of importance. She failed, and went to a woman to enchant her hair to “appear as a field of corn.” Magic had, for some reason, grown strong enough for this girl to reveal her head and have it momentarily be a literal field of corn, with dirt and insects, instead of simply be blonde.
Searching any of these threads never got me an answer, so I hope someone recognizes something here and I can finally put this mystery to rest.