In fairness to hosting providers they are not the reason why your site is slow. These are the questions you need to consider.

1) What is the maximum online users on your site? -- increase the number of mysql connection allowed and RAM maybe too.
2) Do you have several modules from different developers? -- chances are one of them is slowing your site.
3) How many members you have? -- consider adding additional hard drive, maybe a SAS drive then put the dolphin scripts in there.
4) Homepage see more very slow? -- reduced the number of blocks, add .htacesss gzip to compress output, or users not logged in used splash page.

I have more I'll try to add them soon hopefully this would help for the meantime.