Based upon links from a similar question on atmospheric distribution in Chemistry SE, I looked into the latitudinal difference by making a couple images using the MSIS model chemistry plotting website (using Janauary 1, 2016, 100 W longitude, 0 km altitude)

As I understand it, this suggests there is over 15% less oxygen at some latitudes than others. But that it's still approximately the same percentage of the overall air. As to why:

Basically latitudinal differences are due to temperature. Lower temperature means greater air density means more air (and oxygen). See PV=nRT\Charles' Law.
I played with latitudinal cross-sections to see if I could spot any geographic issues, but this image from 30 north (which crosses the dry\arid US desert southwest, the fairly green US southeast, the northern Sahara, dry areas of the Arabian desert, Iran, and Tibet, and then fairly green southeast China:

Still no significant variability apart from temperature.
I couldn't find information on the grid spacing or on what the model accounts for (it could be possible that the model doesn't even take into account land coverage, though that would seem to very poor when modeling atmospheric chemistry!!). But if this model has fair validity, it suggests there generally is very little difference due to landcover over large-areas; wind mixing makes the air extremely homogeneous.
But this doesn't speak entirely to how much very local differences may exist, such as in a parking lot versus a patch of trees. Still, the effects apparently are unlikely to be very significant.
Perhaps walking in the desert is tough primarily because of the dry air\dust\heat\elevation?