There are so many factors involved, especially considering you're on a shared server. It could be a PC-related problem, it could be that the server you're on (not necessarily your site) is under heavy load, it could be the distance from the client's PC to the server.
You can, by all means, try using a new server and see if that helps.