I saw a beautiful explanation by HaKetav VehaKabbalah (Rabbi Yaakov Tzvi Mecklenburg) for the difficulty—it’s a bit long, but I’m bringing it here for the especially dedicated:

HaKetav VehaKabbalah, Deuteronomy, portion of Devarim, chapter 2 verse 29
(29) “Just as they did for me.” This does not refer to passing through their land, but to the matter of selling food and water (Rashi). According to this, regarding what is written in the portion of Ki Tetze, “because they did not meet you with bread and water,” we would have to say that they did not give it to them for free, but they did sell it to them for money, as the Re’em wrote. But Nachmanides already objected to this there in the portion of Ki Tetze, for it would have been enough for a camp like that that they sold to them. Ibn Ezra explained that “just as they did for me” refers to “I will go only along the highway,” just as the children of Esau did for me, for they went around Mount Seir by the highway; and so it is written, “You are passing through the border of your brothers, the children of Esau, who dwell in Seir.” Only the king, who was the king of Edom, did not let them pass through his state, because from there the land of Canaan was near; therefore they passed by Ar, as is written. But on this too Nachmanides wrote: this too is nonsense, for they did not come at all into the land of Edom nor into the land of Moab. See there in Nachmanides, who elaborated on this.

And in my opinion it seems that the verse is speaking neither about the matter of bread and water that the children of Esau and Moab gave them, nor about permitting them to pass through their land. Rather, it speaks about the refusal and denial of the children of Esau and Moab, who paid no heed to the peace proposal sent to them and did not allow Israel to pass through their border. The point is this: after Moses concluded his words of peace to Sihon with a request that he willingly allow passage through his land, and after he assured him that no harm would come to him from this—on the contrary, the people of the country would profit greatly by selling food and drink to such a large camp—Moses nevertheless feared that Sihon might hear about his peace proposal to the children of Esau and to Moab, and that they had refused his peaceful request and had not allowed him to pass, and that Moses had turned away from them and chosen another route. On that basis Sihon might rely and say: I am no worse than the children of Esau and Moab; just as Moses was afraid to fight them, so too he will not fear war with me if I prevent his camp from passing through my land.

For that reason Moses did not refrain from informing Sihon that he should not err in this assumption and think in his heart that he would be like the children of Esau and Moab. Even though Moses had not stirred himself to fight against the children of Esau and Moab and enter their land by force, he would not act that way with Sihon. True, his peace proposal to Sihon was simply a matter of proper conduct and common courtesy, but if Sihon refused permission, Moses would not leave his land and choose another route; rather, against his will and without his consent, he would march with his camp and pass through his land. That is what is included in the phrase, “only let me pass through on foot, just as they did for me,” meaning: if you do to me as the children of Esau and Moab did, who did not heed my peaceful words, know that by force I will pass through your land in order to come to the land promised to me.

Moses did not want to say to him explicitly, “if you do to me as they did,” in order to indicate that he did not suspect him of withholding this small favor—especially when his own people stood to gain greatly from it. Therefore he only alluded to the withholding by the children of Esau and Moab. And in truth the word “just as” can also carry a conditional sense, because the word rendered “that” can also function with the meaning of “if,” as in “if a ruler sins,” and likewise “the blessing if you listen.” And the prefixed letter kaf attached to it is the kaf of comparison and resemblance, like the word “like.” Thus the word translated “just as” contains two meanings: condition and comparison, like the two words “if” and “like.” So the meaning of “just as they did for me” is: if, like what they did to me—that is, if, like what the people of Seir and Moab did to me, you do to me.

And in many verses the word translated “only” appears at the beginning of a statement even though it is connected not to the beginning but to the end, as in Isaiah 28:19, “Only terror to understand the report,” whose meaning is: only hearing the report will cause terror—that is, merely hearing of the punishment will make them tremble and fear. Likewise, “Only for a flood of many waters they shall not reach him” means: even though many waters flood, they will not reach him. So too here: “Only let me pass through on foot, just as they did for me”—its meaning is: only if they did to me as such, then I will pass through on foot. And the word “only” indicates the opposite of what came before: if you grant permission, I will go only by the route designated for an army to pass; but if you refuse my request, know that by force I will pass through your land until I cross the Jordan into the land, etc.

And know that in my view the word translated “only” sometimes means “certainly,” “without doubt”; it is a matter of estimating intent, where one says in his heart: it certainly seems that the matter is only this. Examples include “Surely there is no fear of God in this place,” and “Surely this great nation is a wise and understanding people.” In that sense it can be explained here too: it certainly seems, without a doubt, that I will pass through. According to this interpretation, Moses fulfilled what he had been commanded regarding Sihon above, “provoke him into war,” for there is no greater provocation toward war than informing him that if he withholds permission, Moses will pass through against his will and without his consent. But according to the commentators who interpret “I will pass through on foot” as still part of the peaceful request, it still needs explanation how Moses fulfilled the command to provoke war with him.

And this interpretation is supported by the change in wording here from what he said to the king of Edom (Chukat 20:19): “It is no matter at all; I will pass through on foot.” There he was commanded not to provoke him to quarrel, as it is written above (2:5): “Do not provoke them, for I will not give you any of their land.” Therefore there he said “it is no matter at all,” meaning no harm would come to him, and the end of his words, like the beginning, was peaceful. But here, in order to fulfill the command to provoke Sihon to war, although the beginning of his words was peace, their end was war; therefore he omitted the words “it is no matter at all,” because in truth harm would come through war.

And consider further: there he said, “on foot I will pass through,” and here the wording is reversed, “I will pass through on foot,” because the style of Scripture is to place what is primary first in the statement and what is secondary afterward. Therefore there, where the act of passing through was not primary for him and was not fully settled in his mind, because he was not permitted to fight Edom, he said “I will pass through” at the end. But here, where passing through was fully settled in his mind—to provoke war and to pass through—and it was the main point for him now, he put “I will pass through” first.

And I saw that Rabbi Isaac Abarbanel also explained “only let me pass through on foot” to mean against your will and without your consent; however, his explanation of the phrase “just as they did for me” is strained and far-fetched. And I found a statement of our sages (Bemidbar Rabbah, Chukat, chapter 19): after Israel sent to the king of Edom, they sent to the king of Moab, and he was unwilling. Even though this is not explicit here in the Torah, it is explicit in Judges (11:17), as it says: “And Israel sent messengers to Edom, saying: Please let me pass through your land, but the king of Edom did not listen; and he also sent to the king of Moab, and he was unwilling.” And Moses too hinted at this in the words “just as they did for me,” end quote. It is thus clear from their view that the phrase “just as they did for me” does not refer to giving bread and water, nor to passing by way of their border from the side, as Ibn Ezra held, but rather to the refusal and denial of the peaceful request, as we have explained.