Some clues:
Ping works fine, but website access and utilities such as ssh are slow slow slow!
Memory and CPU usage are all at low, tolerable levels.
I used traceroute, average result is not over 100ms.
This is started on multiple cloud servers at the same time.
Related question: Remote server hangs, gets stuck. How to debug?
I'm wondering where I could look next if the hosting company were unreachable. Any help is of course appreciated.
Try and hook up a packet sniffer (such as wireshark) to the system to see what the network is doing while it's waiting. If you see dropped packets or tons of re-requests, it may give you an idea of what's going on.
Also, I'm not sure what you mean of the example given, 'the issue could be with traceroute'. Traceroute is an application that you'd use to determine how much latency there is between layer 3 links from you to your provider. Maybe they meant you had a high latency between the server and whatever it connects to?
Off the top of my head I can think of two things that would fit the currently available information.
If, connecting to your box with ssh is slow, but when you get the shell it's usable, I would look and see if there's something with either dns and/or syslogd. I've had cases in the past where syslogd were so bogged down that logging your connection took several minutes. The other case I've had have been where reverse lookups timed out rather than returning NXDOMAIN, misconfigured dns-servers for my .in-addr.arpa zones, this goes for both syslogd, httpd and sshd.
Could you try to disable reverse-lookups for syslogd, sshd and httpd and see if that resolves your slowness ? (If it does, I would look into the dns resolver configuration and try to figure out why it's timing out on you).
The other thing that I can think of would case things to be slow could be your IO subsystem being overloaded, you would see this with tools like iostat, sar or dstat. (and possibly also increased cpu load averages).
