For no patient :
lower the maximum returned record count.
Each organiztion run arcgis server on different CPU speed, different number of instance, result in different computing power.
When you publish map service, if you did not change the max number, default is 1000 or 2000. 1000 could result to laggy.
I experienced the laggy and lower the 1000 to 100. No laggy any more.
You don't have to set to 100 if your arcgis server runs on a powerful CPU like AWS EC2, however what is the best number for your server, you have to test it. I use the tools in this website to test my arcgis server performance, get the best number is between 100 to 300. More than 300, arcgis server start to feel laggy.