I had my players run into a hag with a portal they needed to use, in a Planescape game I ran last year. Here was what she asked of them:
"An eye... or a tongue. A sweet memory, or a binding oath of service... or simply your own true name. Oh, there are many nice things you could offer us to let you use our little gate, hehe hehe."
I figured it was best to put the burden of choice on them, as well as let them come up with potentially other offers. Most of the effects were pretty painful, but in my game, the players got away with one of the easier ones - after spending some time debating it, one of the characters realized giving up an eye would be especially appropriate, since they were a Cleric of Odin.
Some of the effects I had in mind for these:
Loss of an eye: The eye cannot be healed, even magically. The character takes a penalty on all ranged attacks and spot checks, and has all forms of vision significantly reduced.
Loss of a tongue: The tongue cannot be healed, even magically. The character can no longer speak or make any verbal sounds at all, and all verbal spellcasting by them automatically fails.
Memory: The character loses their sweetest memory. Though they no longer know what it was, they are haunted by the loss, sinking into a deep depression, giving a penalty to all rolls as they are overcome by despair.
Oath: The character is utterly bound to the Hag's will, and is immediately commanded to stay and protect her. They are retired from adventuring immediately... though she might be willing to bargain with the other PCs to lend her new servant back out, if they can offer her another gift every month...
Name: The character's name is lost. No one can remember their name, and friendly spells have difficulty targeting them. (20% failure rate). They have the same difficulty with their own spells, as well as using magical portals and other devices - it is as though they are somewhat cut off from the world. And they have a strange feeling the Hag now has some hidden control over them... and if they die, they cannot be returned to life without her help, for which she will charge dearly.
I think the real rule of thumb to go by: There should always be a hidden cost beyond the obvious, and nothing should be easy to give.