Shane that is true today and indeed has been the guiding figure for many years (3 mph is usually the Imperial figure used). However in pre technology times when people would walk long distances, not for pleasure but of necessity, I suspect they would have walked considerable faster and quite possibly alternated walking and gentle running.
Depends a lot on the setting of your story allmywires.
Edit: James got in ahead of me. Re the elevation you need to be looking at 3000m or more (10,000 feet) for it to significantly effect your ability to walk. For some, like me, a little less for the headaches to start though