Back in my day, we just played on community servers with moderators who'd just ban cheaters!
I know that's not really a solution with the scale of today's online games, but cheating isn't a new problem. It's only become a problem of today's world of matchmaking systems, global public servers, and the removal of community hosted servers. Still, I feel like just hiring a few more people to manually check suspected cheaters would reduce the need for such heavy handed anti-cheat.
On the other hand, Valve run 2 of the most popular online games (CS:GO and Dota 2), which both have Linux clients, and don't have the same level of intrusive anti-cheat compared to EAC and BattlEye.
Most of these games have not scaled up. "Scale" is not the issue here.
The issue is that companies want to provide their own server hosting, and charge users for the privilege of hosting games. This leaves no room for community moderation.