Gemara

"Regel-Regel" (from Metzora) teaches that the right foot is used for Chalitzah.

34a (Beraisa): We read "Beisecha" like 'Bi'asecha' to teach that the Mezuzah must be on your right side when you enter.

(Rabah): 'Bi'asecha' connotes the way you enter, i.e. on the right.

(Most) people move their right foot first when they begin walking.

37a (Beraisa #1): A left handed person puts Tefilin on his right hand. This is his Smol (weak hand).

Contradiction (Beraisa #2): A lefty puts Tefilin on his left hand.

Resolution (Abaye): Beraisa #2 refers to an ambidextrous person.

Yevamos 104a (Mishnah): If Chalitzah was done with the left foot, it is invalid;

R. Elazar says, it is valid.

(Ula): Chachamim learns from a Gezeirah Shavah "Regel-Regel" from a Metzora. Just like there, we need (to put blood and oil on) the right foot, also for Chalitzah.

Bechoros 45b (Beraisa): If a Kohen is left handed or left-footed, he is Pasul for Avodah;

Rebbi disqualifies an ambidextrous Kohen;

Chachamim are Machshir.

Rebbi holds that his right hand is weaker than it should be. Chachamim hold that his right hand is fine, and his left hand is extra strong.

Chulin 92b (Mishnah): The Gid ha'Nasheh of birds is permitted (because the Kaf (end of the thigh bone) is not round).

Questions (R. Yirmeyah): If a bird has a round Kaf, or if an animal's Kaf is not round, what is the law? Does it depend on each particular case, or on the species in general?

These questions are unresolved.

Rishonim

Rambam (Hilchos Yibum 4:17): If a Yavam's right foot was cut off, and she removed his left foot, the Chalitzah is Pasul.

Ran (Chulin 30a DH u'Makshu): What was R. Yirmeyah's question? Surely it depends on the particular case, like we say that a lefty puts Tefilin on his right hand, which is his Smol (weak hand). I answer that there is different, for the Torah did not say 'Smol', rather, "Yadcha" (with Chaf Hei at the end), which we expound 'Yad Kehah' (weak hand). Normally, it is a Safek. Therefore, regarding Chalitzah, which requires the right (foot), it is a Safek which foot a left-footed Yavam must use. If it depends on him, he uses his Smol, which is his Yamin (primary foot). If it depends on most people, he uses his Yamin, which is his Smol (secondary foot). Therefore, he does Chalitzah with both. However, there is another Safek. Rashi (Bechoros 45b DH Itar) says that we require the right hand and foot, since we learn from a Gezeirah Shavah from Metzora. A lefty Kohen has no Yamin. Also regarding the foot, we require "La'amod Leshares", and a left-footed Kohen does not stand normally, i.e. primarily on his right foot. Since a lefty has no Yamin, a left-footed Yavam cannot do Chalitzah. The Rambam (surely, this should say 'Ramban', like the Beis Yosef's text of the Ran) holds like this. Others say that a lefty is disqualified due to a Mum. We find that one Tana disqualifies an ambidextrous Kohen because his right hand is too weak, and all agree that the right hand of a lefty is too weak. This is a Mum; we do not say that he has no right hand. Therefore, a left-footed Yavam does Chalitzah with both feet, due to a Safek whether it depends on him or on most people.

Ramban (Chulin 92b DH u'Min): Rashi disqualifies a lefty Kohen is Pasul because he has no Yamin. Others say that it is a Mum. This is wrong. This was not listed with Mumim! Rather, it is because he has no Yamin. Therefore, a left-footed Yavam cannot do Chalitzah.

Question (Ohr Some'ach, Hilchos Yibum 4:17): If he has no Yamin, his Avodah should be Pasul! The left hand disqualifies Avodah! All the disqualifications of Kohanim that do not apply to animals are because 'he is not like other seed of Aharon.' They do not disqualify Avodah! This requires great investigation.

Poskim

Shulchan Aruch (EH 169:24): If both one's feet are equal, the right is used for Chalitzah. The same applies if she is ambidextrous.

Source (Beis Yosef DH u'Mah she'Chosav Aval, citing Mordechai in the name of Avi ha'Ezri): This is like we say regarding Tefilin.

Shulchan Aruch (25): If his left foot is primary, some say that he does Chalitzah with both of them. He uses a right shoe on the right foot, and a left shoe on the left foot. Some are unsure, and say that he has no solution.

Beis Yosef (DH Kosav): Sefer ha'Mitzvos says that even a left-footed person does Chalitzah with what is the right (primary) foot for everyone else, even though it is his secondary foot. Semak says that Chalitzah with the left foot is Pasul, even if he is left-footed. Semag says that we learn from Metzora that the left foot is Pasul. Mori says that this is even if he is left-footed, it (his right foot) is considered like his right (primary) foot, since the Torah explicitly required the right foot. We learn a Gezeirah Shavah to require the right ear, and there we cannot say that one is primary! The Mordechai (57) says that he does Chalitzah with both. The Nimukei Yosef (Yevamos Sof 33b) brought also the opinion of the Ran and Ramban that he cannot do Chalitzah at all, and said that the Rashba said 'this requires investigation.'

Rema: The custom is like the first opinion.

Seder Chalitzah (in Shulchan Aruch after Siman 169, Sa'if 26): The judges must know whether the Yavam is left-footed.

Beis Yosef (DH Kasuv b'Orchos): Orchos Chayim (2:13:says that the Yavam must pass in front of the judges from one side to the other until they see with which foot he begins walking. This is his Yamin.

Perush (of the Beis Yosef - 40): I say that if the Yavam has another brother, she must remove both shoes of the Yavam at once, one in each hand. If she would remove one shoe first, perhaps the Halachah is that she must remove the other shoe, and the (first Chalitzah only forbade Yibum, therefore, the second) Chalitzah (permits mid'Oraisa, but mid'Rabanan it) is Pasul, and then she needs Chalitzah from all the brothers. Even though if she removes both shoes at once, one in each hand, it is better to do Chalitzah with the left hand than with the Smol (i.e. wrong) foot, for Chalitzah with the left hand is Kosher, but Chalitzah with the Smol foot is Pasul.

Yam Shel Shlomo (12:22): Granted, Tefilin depends on the weak hand. We learn Chalitzah from a Gezeirah Shavah from Metzora. It should not depend on the person himself (just like it does not regarding Metzora), especially since no foot is stronger than the other, just he begins walking with one of them! Therefore, even a left-footed Yavam should be the same, just like regarding the ear. The Rambam says that if a Yavam's right foot was cut off, and she removed his left foot, the Chalitzah is Pasul. If we use the left foot for a left-footed Yavam, all the more so for a Yavam with no right foot! The Tur and some Acharonim say that a left-footed Yavam should first do Chalitzah with his primary foot. I say that Semag and Semak are primary; he uses the right foot, and afterwards does Chalitzah with the left foot, for a mere stringency. If she did Chalitzah only with his right foot, in pressed circumstances I would permit, but not if she did Chalitzah with his left foot. If she did first Chalitzah with the left foot, she need not do Chalitzah with every brother, like I proved above (3:2), especially since Chalitzah with the wrong foot is not Chalitzah.

Bach (16): My Rebbeyim did not do say to do Chalitzah with both feet at once. Rather, he does Chalitzah with one foot after the other. To avoid a Pasul Chalitzah, the judges warn the Yavam and Yevamah to intend that he permits her only through Chalitzah of the proper foot, whichever it may be. Since neither intended for the wrong foot, the wrong foot did not disqualify her (so the Chalitzah with the proper foot is a fully Kosher Chalitzah).

Beis Shmuel (24): Even though we say that a left-handed Yevamah uses her Yamin (strong hand), we are stringent about a Yavam due to the Gezeirah Shavah. (Perhaps) he needs specifically the right foot.

Beis Meir (Seder Chalitzah 26 DH v'Ulam): I would say that when a left-footed Yavam has another (right footed) brother, we should be concerned for the Ramban and Rashba, and require the other brother to do Chalitzah, even if the -footed brother is the oldest. We must say that the Beis Yosef heard that the custom is to do Chalitzah of both shoes at once, i.e. even if there is another brother.

Note - This is obvious! If there is no other brother, there is no concern for doing Pasul Chalitzah first! Surely, the Beis Meir means 'even if there is a right-footed brother.'