I didn't have that trouble as a Paladin, instead I had the trouble that she appeared way too early. As far as I recall, the conditions are that you can (and did) beat Uhura at both the spear throwing and the bridge fight, and that you went to the jungle as well. It might be that you need to have been judged first instead of just visiting the jungle.
Try and see if any of these suggestions help.

Can't believe I forgot about beating Uhura. Now I feel stupid. Thanks for solving that problem.

Anyone have a good cycle count for DOSbox to get her to show up?

Also, I can't get Uhura to come back to the spear throwing area. She was there the first time, but now I can't get her back for a challenge. Did beat her on the bridge, though.

Don't want to have to restart! If I do, are there any third party tools to tweak character stats?

EDIT: Man, I keep trying. I don't remember it being THIS broken. BTW, am using original Quest For Glory Anthology cd, not the GOG release.

I think that's what causes the leopardman prisoner to appear, actually.

I believe that she only comes back to the spear area if your throwing skill is high enough. Grab some rocks and throw them if you need to tweak your throwing skill. :)

And remember to lead your aim to compensate for the wind. Your cycles do need to be pretty low to prevent the wind from changing like a tornado.

I think you could also decrease the speed from the options, and I'm not sure if QfG3 also had a skill or difficulty setting there as well. I do recall being able to throw spears with no wind at all, so I guess it has a difficulty slider, which if it's on the lowest setting, you wouldn't have any wind.

Of course my memory is known to play tricks on me, so take it with a grain of salt.

Hmm, then my game really is broken. I've tried 3 runs that played like speedruns, one time holding off on making the dispel potion until the prisoner showed up. Beaten Uhura on the bridge, everything should be set. But the prisoner just will not show up.

Alright, got it done. Left DOSBOX at 3000 cycles, got throwing skill to 175, Uhura showed up, prisoner showed up, game finished. Now on to the vastly superior QG4, heh.

I have another problem with the leopard woman. I got the permission to "marry" her, but after giving her the fine dagger, the wooden leopard and the beads I am not allowed to open the cage, and Uhura says I still have to give a token of friendship. Any clues?

If I remember correctly, you have to free her, when the other guard is, uh, guarding.

He will mutter something but if you have given all three tokens, she will follow you into the jungle.

Unfortunately, Uhura is somewhat unhelpful there since the leopardwoman really wants her freedom more than anything else, and the 'generic' guard is the only one who will actually let you give it to her!

The only thing you actually need to trigger the appearance of the leopard woman in the village is to accept Uhara's challenge in spear throwing, and complete it one time. You can lose; winning does not matter. The bridge challenge is also not important. To make her appear to challenge you, you must have a Throwing skill of 125.

For freeing her, she needs to be dispelled. Complete the manhood trial (as long as you help Yesufu when he is stuck you do not have to win), talk to the Laibon about the bride price, exit, reenter and talk about marriage. As long as you have the items for the bride price, you will buy her freedom. Head to the cage. If Uhara or Yesufu are there, leave and immediate reenter. You do not have to give her gifts; as long as it is the nameless guard, you can open the cage and let her out.

When she runs off, head to the jungle and she appears as a random encounter. When you get an encounter with no monster, use the Mouth icon to call put to her.

I posted a speed run on Youtube. Look up mrprmiller and I have routed the first four games, and have posted speed runs of all the classes for them. They are Any%, so they do the minimum neccesary. There is a Paladin run of QFG3 too.

If she is not appearing with the Paladin, it is probably bad RNG or you have done extras that are not required that have short circuited the event from firing, as you do not need anything other than that to complete the game by that point. My speed runs are run on the GOG releases, so I know it works.

In addition to the Throwing skill requirement, I believe there may be a Strength requirement as well. I was having trouble getting her to show up even after maxing my Throwing skill, but she appeared right after my Strength hit 200 (my character was a Wizard before becoming a Paladin, so his Strength was pretty modest. This is probably why the issue only seems to occur with Paladins rather than pure Fighters.)

If you're a fighter or paladin, beating Uhura at spear-throwing is what triggers the leopard woman appearing. Uhura will come back to challenge you when your throwing skill is 175.

The best way to improve your throwing skill is to go out into the savannah, pick up a ton of rocks, and throw them at every monster you encounter until they die. Yes, you can do that in "Quest For Glory 3." If you throw enough rocks at a monster, they will die before you have a chance to fight them. It's quite an efficient way of killing monsters and improving your throwing skill. This doesn't work too well in the first 2 games because you'd have to type "throw rock" every time. In the 4th game it only works on the revenants. The other monsters move too fast. In the 5th game there's no point because of the way the combat system is designed. But in game 3, throwing rocks at monsters 'til they die works like a charm and is the fastest way to improve your throwing skill

You don't even have to hit anything. You can throw the rocks straight into the dirt and your skill still goes up.