There isn't really a "best" order, since the game is about doing things in your own way. My first playthrough of the game went like this: Ruta, Rudania, Naboris, and Medoh. In more recent playthroughs I've done Medoh first to get Revali's Gale early, but it depends on the player and the experience they want to get out of it.
Doing ruta first sets you up for disappointment because the others and their quests are much worse.
I did naboris first, which was probably the hardest one. No regrets.
Doing Medoh first is probably most handy for that power though, and the divine beast dungeon was pretty good.
On my second play through, I did Ruta, Master Sword, Naboris, Medoh, and Rudania.
Although Naboris is a huge pain in the ass, the Master Sword breaks Thunderblight easily once you get the timing down of its attacks. Miphas Grace and Urbosas Fury pretty much set you up for the rest of the game.
I think starting with Medoh and ending with Naboris is the best. Medoh first because the champion's power opens up your paths of traversal even more. And Naboris last because it is the most challenging (and interesting IMO) out of the four, so you get to work up to something.
If I was to give just one recommendation, I'd probably take them in the following order:
1) Medoh - because of the champion's power aiding your traversal
2) Rudania - because the campion's ability will further aid you when encountering enemies
- also, these two are the easiest out of the beasts, and have the easiest boss fights
3) Ruta - because by this point the champion's power actually gets more worthwhile (in the beginning you get essentially the same effect with fairies) and the dungeon/boss is more interesting than the previous two
4) Naboris - end on a high note, the most interesting dungeon and most challenging boss fight, and because the Yiga attacks ramp up after doing this quest