You put your right foot in ...

The shulchan aruch (O"H 2:5) writes that when one takes off their shoes they should start by taking their left shoe off first. This is true for both a right handed and left handed person since the issue at hand is the respect the Torah gave to the right (The ritual of the metzorah involves applications to the right toe and thumb [Taz] and the avoda in the Mikdash is only kosher with the right [Aruch HaShulchan]). The Aruch HaShulchan points out that it is a honor to a limb when it is dressed, so we want to keep the right side with the shoe as long as possible.

Maran HaRav Kook Zt"l writes in his chiddushim that this din is different when we take off our shoes in order to perform a mitzva. When the purpose of taking of the shoe is a mitzva, then it honors the right to be the first. Thus Rav Kook paskens that when taking off shoes for birkat Kohanim, the right shoe should be taken off first. The same goes for erev Yom Kippur. This is not the case, however for an avel or on erev Tisha Be'Av. These mitzvas are not happy ones and thus it would not be proper to honor the right with a mitzva of mourning.