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.