I am an aerospace engineer, who has worked on the design and certification of pressurized aircraft, so let me try and answer.
The class of regulations that deals with the certification of pressurized aircraft are called 14 CFR 23.841 (General Aviation) and 14 CFR 25.841 (Commercial). Both paragraphs are pretty much identical and in summary say the following (paraphrasing):
All GA and commercial aircraft designed and certified to cruise at
altitudes greater than 25000 ft must be pressurized.
This means that aircraft whose maximum altitude (often referred to as "service ceiling") is less than 25000 feet do not have to be pressurized (once you exceed 14000 feet, most people begin to use supplemental oxygen, but above 25000 feet your plane must be pressurized and that's what provides your supplemental oxygen).
Unpressurized GA aircraft routinely operate at altitudes up to 25000 feet. This should answer what pressurization an airliner must provide at high-altitude airports: None! Not unless said airport was above 25000 feet would some pressurization be required (a problem that does not exist on this planet).
What paragraphs 23.841 and 25.841 are saying is that those airplanes that are pressurized, must be capable of providing cabin altitude of no more than 8000 feet at their operating altitudes. So consider two aircraft, one operating at 25001 ft and the other at 45000 ft. Both must provide no less than 8000 feet in the cabin. It shouldn't come as a surprise that the one operating at 45000 ft will require a stouter (i.e. stronger and thus heavier) fuselage as the pressure difference between the cabin and outside is much greater. Many modern commercial airliners provide a 5000 feet cabin altitude and some bizjet manufacturers are already considering sea-level pressure in the cabin, but I digress.
Anyway, I hope this sheds some light on this mystery. Cheers.