What was the fantasy novel with a fire/fertility goddess named Fala and a sea god named Sur?

Question

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.

Answer 1

This might be Sorcery Rising (2002) by Jude Fisher (Jane Johnson).

The goddess would be Falla, goddess of fire:

Instead, they prayed to some fire deity, a creature-a woman-rumored to have come walking naked out of a volcano in the Golden Mountains, unscathed by the lava, leading a great cat on a silver chain. Falla the Merciful-that's what they called her

There is also a god named Sur:

It was here-according to her folk, the Eyrans, the people of the north-where their god Sur had first taken his rest

Who makes his home in the sea:

he had raised a great stronghold beneath the waves, deep down on the ocean bed.

The women of the south (Istria) are veiled, revealing only their lips:

Fent grinned appreciatively. "Incredibly seductive, being able to see nothing of them but those painted lips."

The scene with the hair:

Wave upon wave of shining hair tumbled from the confines of the silk, transformed by the nomad charm even as it escaped its bindings. "If you really want him to notice you," Fezack Starsinger had said, "you must wait till his eyes are upon you and you have his sole attention."

"I want it to look like a sea of corn," Jenna had said, imagining a cascade of gold, a gleaming, textured sea.

Now that phrase came back to plague her.

Had she stipulated ripe corn, it might at least have ameliorated the color; but she had not paid sufficient thought to the wording of her wish: green it was, her hair; as green as any new crop. And the magic had not stopped there. Out of the sheeny green tumbled field mice and bees; earthworms and loam. People close to her swatted at their faces, picked up their feet. A lark burst from her mane and soared up among the mast-pillars, where it trilled in panic.