I have rarely lag, and I don't have one of the greatest computers. I haven't tried AI in multiplayer, but like the others said, if you can do multiplayer, then do it without AI. But if you want to hear another story:
1) Make sure all internet connections are good.
2) Don't use Hamachi, I don't remember it performing well, and I do remember it causing lots of issues, as if it was some kind of malware. Most people are on Gameranger/ESO, so play there, both function ok, and it helps to get people in your games instead of bots, who are designed for single player. Gameranger also works through the lan function, so maybe you want to go there.
3) Make sure everyone has a good computer. I think processors are the most important factor for the AI. This game isn't optimized for multiple processors, remember that when buying a new computer.
4) Make sure everyone isn't using the battery saving power option.
5) Don't use gigantic maps, and don't let the game hit the point where thousands of units are present. Try to finish games within the first 30 minutes.
6) Bump down your settings. IIRC, if your graphical card cannot process everything, it will push the process to the CPU.
If all that didn't work: learn XS coding, and code the AI to be even less performance heavy.