Minecraft Legends just recently released on Steam and sadly at release it just wouldn't run, a quick bug report later and Valve has already solved it with Proton Hotfix.
Initially trying through any Proton version tested it just wouldn't load, and it was the exact same problem on Steam Deck and my Fedora Linux desktop. It would just bring you right back to your Steam Library. I opened a bug report and now thankfully it's solved. So now as long as it's set to Proton Hotfix, you're good to go. Valve have set Proton Hotfix on it, so as long as you're not forcing a different version, it will pick it up automatically.
Once again, Valve and their developers working on Proton have reacted very quickly to a brand new release, which is really good to see. I have found that sometimes it will just randomly crash though. Not overly often but it does happen.
For Steam Deck, you'll want to drop it from High to Medium in the graphics settings, which seems to give overall a rather stable 60FPS and it's very smooth apart from minor loading hiccups. On High settings on Steam Deck, it will dip down to 40FPS and sometimes below, so still doable but honestly it's perfectly fine on Medium and looks great.
Another issue I noted, specifically on desktop Linux with the Stable Steam Client, is that the Microsoft Account login was just a blank window in the Steam browser that pops up. However, if you simply resize the window, it then renders correctly. There's an existing bug report for this for the main client. The login there worked fine.
For Steam Deck, the login may seemingly not work getting stuck after entering a password, but reloading the game showed me logged in just fine. You can also try the login on Desktop Mode on Steam Deck but for me in Gaming Mode simply restarting after waiting a minute after entering password worked.
So a few quirks but overall once you in, it performs great and looks great with Proton Hotfix.
You can buy it on Steam.
ICYMI: Valve recently released Proton 8!