I swear if I see right to lifers gathered in the Hydlaa plaza with placards, draping passerbys in floral wreaths, linking arms and singing kum by ya.. there will be a bloodbath.
Personally I like the gibbet option. Hanging in the sun, swinging in the breeze and eaten by the crows over weeks. The stocks when combined with the Cat\'o Nine Tails makes for a good public spectacle too, a few floggings are usually deterrence for all but the most hardened crimainals.
Maybe people can be permanently disfigured as a result of their crimes - steal, and you lose a hand. Permanently! Never being able to use a 2-handed weapon, bow, sword+shield, etc ever again. Or for those really sadistic folks perhaps branding the crimes that the person has committed into their flesh in a visible body location with hot iron.
I think seeing a maimed and very sorry looking ylian or enki limping around the city minus a paw/hand and with raised welts visible on their back would send a strong message.