Webm format should work on Steam Deck - we have an intro video playing in our game on startup, no user interaction required.
You don't need both webm and mp4 files, just keep the webm one.
Hmm it still doesn't work for me. I'll try my backup plan of converting the videos to gifs/animated sprites and running the audio alongside.
UPDATE: Thankfully, I got the video-playing working on Steam Deck after all. What seems to have happened is that because C3 didn't tell me whether or not the filenames typed in the events needed to have the ".webm" extensions included or not, I went with duplicates of the play events, repeating the play event one with and one without the file extensions, assuming the right one would stick. It seems this worked in preview, but not on Steam Deck, if that makes sense that that would happen. So I only kept the events that included the extensions and it now works.
I do have a small suggestion from this though: that C3 simply include the fact that you need to include the extension for videos (stated in C3 itself, not just in the manual). That would've likely helped me avoid this complication. Thanks!