The problem was setting the appropriate file permissions for the Linux executables. I don't have a Linux machine, but I do have a tiny command line application for Windows that can set the executable bit for the appropriate files and pack the build into a tar.gz archive, thus preserving these permissions. But while Itch.io supports uploading tar.gz files, Steam doesn't; it's either direct upload or zip files.
What changed things is that recently I was given a macbook at my job, and because macOS is built on Unix, I was able to set all correct permissions there and upload my files directly from that laptop. It was a bit complicated to set up at first, but now it's running like a charm.