Interesting question! I learned from it while finding my sources, so thank you!

In certain contexts sandals were indeed associated with royalty amongst the Aztec and other Mesoamericans. However, I think there are two important things to consider:

1. It wasn't just "sandals," it was specific sandals in specific places, with important attributes, that were associated with royalty
2. As far as I can tell, sandals weren't a uniquely important sign of royalty

I'll talk a bit more about each point.

The first thing I'm trying to say is that the connections between sandals and royalty in the Aztec world were specified by place and presentation of those sandals. Here's a quote that addresses what Mexica lords probably wore for major state events:

the coyolnacochteoxihuitl (earplug of very fine turquoise with bells), the xiuhmaquiztli (bracelet with turquoise)...the xiuhchimalli (turquoise shield), and the xiuhcactli (turquoise sandals). Mexica emperors would have been laden with turquoise covered garments and other accessories. The significance of encasing the supreme lord with turquoise insignia relates to the symbolic value of the stone in general (Aguilera 1997: 9)

So the reason for the sandals' importance here is clearly associated with the value of turquoise and its associations. They weren't important for being sandals; they were important for being sandals that had special features. This is true for other cases as well:

Moctezuma’s sandals [had] gold and precious stones on the upper part. Sahagún...mentions rulers’ sandals of ocelot skin or decorated with embroidery (Boone 2017).

Clearly, these weren't just normal sandals, and it's arguable that their "sandal" aspect was less important in signifying nobility than their decoration. Obtaining, working, and adding these materials to sandals would also have involved significant effort that made the shoes more difficult to make than simple straps. The importance of context for the sandal-nobility connection is also clear in when they couldn't be worn:

rulers and nobles did wear sandals, and commoners were forbidden to wear them in the city...rulers and nobles went barefoot in the presence of the supreme ruler Moctezuma and in the royal palace (Boone 2017).

So wearing sandals depended upon who you were in the presence of. Again, this doesn't necessarily mean that the "sandal" nature of the shoes themselves marked royalty at all times. It does emphasize how royalty and power was coded into dress as a means of who could wear what given which contexts.

Finally (on the sandal front), there were many items much more important to the Aztec than sandals in signifying royalty. Some of these were qualities or materials, such as the ocelot skin, precious metals, or turquoise colors mentioned earlier. Others were individual items. For example, the xiuhitzolli turquoise diadem portrayed here and reconstructed here were reserved for the leaders of independent cities. (Aguilera 1997).

As to what this means about other people going barefoot - the fact that commoners were forbidden to wear sandals in Tenochtitlan suggests that at least some of them did wear those shoes outside of the city. Clearly, going barefoot was more normal in the Aztec world than it was in, say, medieval Northern Europe. But logistical reasons like temperature would have influenced this in addition to cultural factors.

​

edited to clarify sources

Aguilera, C. (1997). Of Royal Mantles and Blue Turquoise: The Meaning of the Mexica Emperor's Mantle. Latin American Antiquity, 8(1), 3-19.

Boone, E.H. (2017). Who They Are and What They Wear: Aztec Costumes for European Eyes. Anthropology and Aesthetics 67.