There's a sense in which the (natural?) way God made things is better (or, at least preferred by God) than any way that humans have added to or modified his creation.
Altars and Monuments
Not all altars were made of stone (notably the bronze altar in the tabernacle), but most probably were.
Exodus 20:25 (NASB)
"If you make an altar of stone for Me, you shall not build it of cut stones, for if you wield your tool on it, you will profane it."
(Also: De 27:5, Joshua 8:31)
The people who built Solomon's temple employed this strategy. (1 Ki 6:7)
The monument set up when the Israelites crossed the Jordan to enter Canaan consisted of 12 stones taken from the river that were not worked or shaped in any way. (Josh 4)
The people were not to attempt to make/fashion idols that resembled God. Why? Perhaps the fact that people imaged God far more/better than anything humans could craft is part of the reason behind prohibiting these images. What God made and did is best for this purpose.
Rather than being about shoes, I posit that being barefoot (as God made mankind) is a manner better suited to standing (closer) in his presence, which Moses did at the burning bush.
For the priests (Ex 28, Lv 16:4), there is a list of special clothes they are to wear when performing their duties, and footwear is absent from the list. Jewish tradition (Babylonian Talmud 2,1) said that nothing should come between the priest's body and the floor, so the priests always offer(ed) their service barefoot.