I think I'm using a virtual dedicated server or VDS.
The hosting company has been extremely helpful, but they haven't been able to identify the problem. I asked my friends from the States to check the site speed... One time, they said it's very responsive; later, they said the site crawls.
So, I'm somewhat frustrated.
And no, I don't have any accelerator installed, but my host is working on it.