The Shulchan Arukh states that we should don our right shoe first, and then the left; but tying shoes is in the opposite order – first left, then right. (SA OC 2:4.)
The source for this law is in the gemara Shabbat 61a. Rebbe Yochanan states that the left shoe should be put on first, since shoes are likened to tefillin which are tied on the left arm. Yet there is a baraita which states that the right shoe has precedence. The gemara concludes that we can fulfill both views by putting on the right first, according to the baraita, but respecting Rebbe Yochanan’s view by tying the left first. The idea is that the likeness of shoes to tefillin is primarily in the aspect of tying; therefore, even according to Rebbe Yochanan the main importance is to tie the left first. (See Tosafot.)
And why are the tefillin tied on the left arm? The gemara in Menachot (37a) gives two reasons: the first is that we tie the tefillin with the right hand, just as we write the parshiot with the right hand. The second reason is that the Torah tells us that the tefillin are a sign “al yadekha”, “on your hand” (Shemot 13:16);the expression is written in an unusual way which can also be read “al yad keha”, “on your weak hand”, meaning on the left. This second reason is the one cited by Rashi in the gemara in Shabbat.
We can explain this as follows: the right side represents the aspect of mercy; the left the aspect of stern judgment. We see this in the vision of Zecharia who sees Yehoshua the Kohen Gadol standing for heavenly judgment; on Yehoshua’s right, meaning the left of the Judge (the angel of HaShem), is Satan, who is the accuser (Zecharia 3). The Malbim explains that the accuser stands to the left of the judge.
Both aspects, mercy and judgment, are necessary; the Midrash (on Bereshit 2:4) declares that the world cannot stand on either aspect alone. However, the balance is not currently ideal; there is too much judgment and not enough mercy in the world. We find many times that our Sages indicate that we should work to strengthen the aspect of G-d’s mercy and limit the aspect of His judgment. For example, we find that Rebbe Yochanan urges us to pray that from above they should augment our strength and dispel our adversaries; Rashi explains that this means to strengthen the aspect of mercy and dispel our accusers (Sanhedrin 44b).
Thus there is a need to bind or restrain the left side a bit, though this should not be taken to an extreme since after all the aspect of judgment is still part of Divine justice. (See Darkhei Moshe OC 131:4 who explains that for this reason we don’t lean on the left arm during morning tachanun, when we are wearing tefillin. My understanding is that leaning on the left side and tying the tefillin on the left side both express restraining the aspect of judgment.)
We have explained in many columns that wearing shoes represents our special human status; they separate and protect us from the lowly ground, and are typically made of leather showing that we are elevated above the beasts. Thus when we put on our shoes showing strength and protection, we give precedence to the right. But when we tie, showing restraint, we give precedence to the left.