Each graphic in the map has to be converted to json and sent in the webmap json to the print service. So graphics and layer that are added at runtime can cause a slow print. I have also run into a case where the AntiVirus on the ArcGIS Server where the print service is running caused a significant delay.