Sharing some research I did, I found that it's possible to get Sandals (and seemingly every item including uniques) from the very first barrels of the game.

Therefore, there is a strategy you can use where you start the game, break the closest set of barrels, and if you don't get a Sandal or a 2H weapon (As recommended in the speedrunning guide as the most important item drops), then you simple quit and try again.

When I tested it, I got a sandal after maybe 10 tries. This is confirmed. Considering this is a 10% speed boost, this alone would be good.

I didn't get a 2H weapon in my limited tests, but by ram hacking and trying 64 different item drops in order, I found one 2H weapon. It seems there are 640 possible drops before it cycles back around. My drop table notes are here https://pastebin.com/g2E7xDGG .

This means if you break 4 barrels, you should see (on average) every item once every 160 tries, including every unique item. However, I might have misunderstood something about how the RNG works. It's possible that there might be something that prevents you from getting a 2H weapon dropped before you reach a certain level, perhaps.. I'm not sure. I didn't see evidence of that, but others who are more familiar with the game may have noticed something like that.

Currently afaik, no runs have tried using this technique, so you should consider this as a possible route to a new gold record ;)

I could do a bit more testing and see how frequently Sandals show up for different characters, if it's really about a 1/10 chance that's not too bad, but I'm a little skeptical based on experience. It's worth noting that a 2H sword (or hand-and-a-half sword) is only important for Eowyn's run; Aragorn should use two 1H swords instead. With that in mind, I'd say the best thing to reroll for would be a 2H sword for Eowyn and Sandals for every other character, provided a 2H sword isn't obnoxiously rare.

As for actual viability doing runs, it's hard to say whether it would be worthwhile. It certainly could be, and I don't want to deter people from trying this, just want to share my thoughts on it. There are a couple things to consider from a competitive runner's perspective, particularly when it comes to Sandals:

1. Sandals are a very common early game drop, so you'll often end up finding a pair somewhere in the first few screens of the game anyways and it's hard to say whether the time it takes to move to and attack all the barrels/stumps can be made up by the extra speed before you would have gotten Sandals anyways. I found Sandals relatively early in all of my WR runs for the New Game categories.

2. The entire game is very RNG-heavy, so resetting numerous times to find Sandals immediately will by no means guarantee that the run will end up better than if you didn't worry about the barrel drops at the start. You might be starting with 10% faster movement speed, but if you don't also find a strong weapon you'll have trouble killing enemies quickly.

Neither of those points apply the same way when considering a 2H weapon for Eowyn, however. If you find one of those at the start of the run it will dramatically reduce the time it takes you to get through the early areas of the game and will be useful throughout the entirety of the run as well. If resetting for a 2H weapon is viable (i.e. not a terrible chance), I would consider attempting that for runs, but I don't think I would reset for Sandals personally. Of course if anybody else wants to do so, I don't think it's really a bad idea at all, so you should go for it!