You can make a pretty good experience server side anti cheat and authoritative networking. Trust factor systems like CSGO has also work well (as long as you prevent abuse which is basically what went wrong with CSGOs implementation). You can also design your game in a way where cheating just isn’t effective (e.g. rocket league).

Ultimately the best way to have fair games is to promote finding players through avenues other than official matchmaking: friends or even just random people on something like discord.

I imagine you could implement a majority of what traditional anti-cheat software gives you as a server-side machine learning algorithm. In my experience as a gamer, the vast majority of cheaters are completely obvious, so that would likely be as true for machines as it is for human players. This comes with the added benefit that your anti-cheat mechanisms would be much more difficult for cheaters to reverse engineer, since they won't have access to the binary. Of course, I'm not aware of any such off-the-shelf solutions, so this point is moot for indie developers who can't afford to build their own anti-cheat software.

Disclaimer: I'm not a game dev and don't really know what I'm talking about.

Don't play multiplayer games on Linux.

I don't know. Maybe server-side analysis? Just don't ship borderline malware kernel modules and there will be no problems.

Dedicated servers and active admins.