So I called my hosting provider as to why Magento is unbearably slow when they host it and 10 times faster when I copy the installation precisely onto my home computer.
You've already answered your own question.
If you have better performance after mirroring the site elsewhere, then the environment is at fault.
Contrary to popular belief, there isn't anything particularly wrong with Magento shared hosting - as long as the hosting provider doesn't oversell and knows what they are doing.
Ask a few other web hosts for a free demo - and you'll have a definitive answer.
I was guessing, a dedicated server would help with that because it will deliver more performance
Dedicated hardware is always going to outperform anything else (shared/vps/cloud), but whether you need that capacity is up to you to determine.
My advice to merchants is that the tipping point for going dedicated is when you have in excess of any of the following,
- 1000 unique visitors per day
- 10,000 products
- 30 orders per day
- Heavy API integration/activity
Why does the same installation run so much quicker for me if it's REALLY not about hardware?
Hardware
Hardware sets the baseline for performance, if you've got slow/outdated kit, you'll have a ceiling on the best performance you can see.
Software
Software configuration (ie. OS - MageStack or Centos/RedHat ~cPanel/Plesk/Interworx) will then be the second factor that sets the limit on performance. A poorly set up server through poor OS choice is again going to cap the best performance you can see.
Code
Finally, the store itself is going to be the final determining factor. Your choice of (or volume of) 3rd party modules and template are going to dramatically affect performance.