Your are wrong. Partially
Where you are wrong: Barometric pressure drops relatively linearly as you increase altitude (it actually drops a bit quicker across the first 1000m in increasing altitude). While the percent inspired oxygen (20.9%) is the same at all altitudes, the partial pressure of oxygen drops along with the barometric pressure. The partial pressure of oxygen is the driving force for gas exchange in the lungs. So, in Salt Lake City, you are getting about 14% less oxygen per breath, in Denver, about 17% less, and in Flagstaff, about 23% less. So not exactly an order of magnitude difference.
Where you are right: the binding ability of hemoglobin to oxygen is not a linear relationship. The binding ability decreases with decreasing oxygen pressure. The disassociation curve describing hemoglobin's tendency to bind oxygen shows that the ability to bind oxygen decreases slowly until about 6500ft, then starts to decrease much more quickly. So while I think it is still a stretch to call it an "order of magnitude" difference, you did correctly observe that the effects of altitude increase more quickly after you get to altitudes of those similar to Flagstaff.
I think the NCAA conversions do a decent job estimating these effects. Check out their conversions and compare times between SLC, Denver and Flagstaff.