Okay, I have now had the time to do some more debugging. The video container or codec wasn’t the issue.
It turns out that the screen size was scaled. Although the videos were shot in full HD (1920x1080), I was running the experiment in the resolution of my external monitor, which was 2560x1440. I believe this put a very heavy load on PsychoPy to scale the video to the correct resolution. The video played just fine in h.264 mp4 and moviepy backend at the native resolution.
Problem solved! Thanks a lot for the help though, mdc!