I'm pleased to announce that I finally managed to get it to work. There's just two things you need to know to get the native Linux version running on the Steam Deck:
1) Make sure the filepaths are correct. BoilR messed this up when importing the game through itch, I had to go to the game's properties in Steam and manually browse to the appimage again for Steam to fill in the correct filepaths.
2) You need to use "--no-sandbox" in the game's Launch Properties from within Steam.
And boom! Works perfectly fine! I personally recommend changing the left joystick in Steam Input to mimic the d-pad, so you can use both the d-pad and joystick to move.