With the help of this forum post and a bit of persistence I managed to get it to work and I wanted to share how with future generations and/or my future self.

First Problem: libstdc++.so.5
dnf does not have libstdc++5 but apt does.
Solution: I installed Mint on a Virtual Machine ran sudo apt install libstdc++5 and then copied the library to my real machine into the system directory of UT2004. The game now starts. I know there must be a better way to solve this.

Second Problem: Game starts in a tiny window stuck in the top left corner
Alt+Enter switches it to a real window that makes the game useable, but setting a proper resolution and trying to make it fullscreen again crashes the game.
Solution: Open /home/odin/.ut2004/System/UT2004.ini, go to the [SDLDrv.SDLClient] section and set all lines with viewport to the desired resolution.

Third Problem: No sound
UT2004 uses the obsolete OSS sound system.
Solution: Run the game under a compatibility wrapper. Debian and derivatives have aoss available. Fedora and derivatives have padsp. Thus run the game with padsp "./ut2004-bin-linux-amd64" and the sound works.

If all else fails I’ll fall back to the Windows version, would make me very sad though.

That helped. Thank you very much! Crashes everytime I try to switch to fullscreen though, I’ll play around with it for a bit, hopefully I’ll figure it out.

The DVD includes SDL and OpenAL, but not libstdc++

Right. I tried that patch now, but it still wants libstdc++.so.5

To be honest I’m having way less problems than I was expecting. I would never want to switch back.

Well yeah, but how do i figure out which version I need and where do I get that version?

Well obviously the version on the DVD is ancient. I did apply the latest available patch, but that is also ancient.

I assume the steam version the Lutris script uses was updated at some point after the last retail patch.