In RL, we need a good reason for running, as most people would avoid sweat, fatigue and muscle pain outside of sports.
In PS, we need a good reason to walk, as running has all the advantages. So yes, keeping the stamina stable, or even rising, may be a good option. Another could be to allow certain actions when walking but not when running (eating, drinking, casting spells...?)
But the carried load has to be the main part of the equation. At full charge, no running at all, and exhausting walk.
Two speeds of running would be good as well: one for traveling, one for fleeing.