Try installing the flatpak version.

Install the ffmpeg version that matches the firefox runtime (mine is 23.08):

flatpak install org.freedesktop.Platform.ffmpeg-full

Can you provide a link to a video that fails for you. What desktop? X11 or Wayland?

Just for S&Gs, I downloaded 113 and both sites work for me. see screenshots

Operating System: openSUSE Tumbleweed 20240126 KDE Plasma Version: 5.27.10 KDE Frameworks Version: 5.114.0 Qt Version: 5.15.12 Kernel Version: 6.7.1-2-default (64-bit) Graphics Platform: X11 Processors: 12 × Intel® Core™ i7-9850H CPU @ 2.60GHz Memory: 125.1 GiB of RAM Graphics Processor: Mesa Intel® UHD Graphics 630 Manufacturer: HP Product Name: HP ZBook 17 G6

Maybe try to match what I have installed and see if it works. I had issues on my other laptop running Leap, but after matching the ffmpegs that are installed on my other laptop running Tumbleweed, videos are now working. I know your distro is different, but see what you can do.