It's kind of important to know where the bottle neck is when dealing with lag for any computer game. The "server is ahead" message suggests that the client computer can't keep up with the computations happening on the server. This suggests two things:
1) Network packets are taking a long time to go between the server and client
2) The work the computer does to process the packet is too much (maybe because the packets require a lot of processing or there are a bunch of packets that require work)
In case 1, you can only really get a more stable connection or move closer to the server to resolve the bottleneck.
In case 2, your CPU is just too slow or (very rarely you have not enough RAM or the read write time on the RAM is too slow if you're using something from the 90s). Typically, what's consuming the most CPU cycles are simulating physics and units. The network packets tell your CPU what the new orders are from every player, and your computer has to simulate the physics and unit movements. More players, more orders to process and simulate.
I'm not sure if there's logic for AI players to disable each other and only have one AI issue orders, but if you ever spectate an AI game, you will see the AI is constantly spamming orders.
Graphics cards typically do two workloads in modern gaming, physics and rendering graphics (think shaders, drawing triangles on the screen, putting textures over meshes, etc). Yes, lowering graphics means your GPU is gonna render each frame quicker. Sometimes this translates to your computer handling physics frames better because there's less CPU overhead with moving stuff to and from the GPU. Great. But if you lower graphics all the way, and you're still 10 minutes behind the server simulation, well graphics probably isn't your biggest bottleneck.
