That's interesting.
The hardware on my part is an original steam deck plugged into a dock so I could use it as a desktop PC and my monitor is just a regular 1080P one.
Alright, I was able to confirm this was a Linux specific issue. I haven't identified the exact cause yet, but as a compromise I made it so fullscreen for the Linux build just gives you a larger field of view, basically instead of black bars preserving the snes aspect ratio, you can just see more at the sides of the screen.
I can confirm that this works on Ubuntu 24.04 LTS, so I expect it should work on the Steam Deck. Your save data is stored separately from the game files so you should be able to replace them safely. Try replacing your files with the new build and let me know if it works!