Magento is a fantastic and flexible shopping cart platform. However it is complex and not for the average developer to handle. It requires specialist Magento developers. It also has specialist resource requirements beyond the average web hosting account and beyond the average developers skills to setup.
If you are trying to setup Magento on shared hosting forget it now! Even on expensive large shared hosting accounts your Magento site will never get enough resources to run well. The best you'll ever get is very slow.
The ideal is a small VPS or Droplet. Both require expertise to run and setup, but they are really the only way to make Magento run well. Basic requirements would be 2Gigs RAM for a very small site and many more for large sites with large traffic volume.
You'll also need to make sure its running PHP5+ and MySQL...no Windows servers it must be linux.
Cache and caching modules
Without specialised caching Magento is practically garabage (similar to most carts, Wordpress, etc). Firstly you need to have Magentos caching on, without this forget it your dead.
Secondly you'll want to be running in a system that is running Varnish, Pagespeed, xCache or some Magento specific configuration. These options are all server based and require a far bit of configuring, so if you have gone for a managed VPS you'll need to be able to do this or have someone at hand to do it. There are also full managed systems of different types offering Magento specific services, such as Mebsites Magento hosting.
Static Content servered from CDN
This can be a great way to server pages offshore (if your Aussie based) and retain some speed. It also can improve performance if your server is a little slower due to budget constrants. Essentially your pages are cached in memory with an external service and displayed to the user from the closest fast cache, see Cloudflare.com. As a bonus these CDN services offer a lay of protection against DDOS attacks and many basic hacker attacks, because it is very difficult for the hacker to interact directly with the server as they can only access the content in the CDN. Cloudflare also offers SSL encryption.
The downside sometimes is if you have a very high performance server you may have a reduction in performance. The other is sometimes the compression maybe interfer with the theme breaking it. Thirdly because everything is cached you will need to manual update the caching in your CDN or wait for it to refresh both options are not instant. In some cases this is desirable others its a pain.
Cheap developer = Bad code
Magento developers are more expensive and run of the mill coders for a reason. Mistakes or poor coding can destory an chance of speed. Often I see this with cheaper outsourced developers ...however maybe its better described in these terms. They don't need to worry about the day to day operations so they don't code for it. So beware cheaper short term can cost you your whole development long term.
One very cool thing about magento is its databasing can be broken down it to separate parts. You can have a vps for serving images, vps for products and then you can customers of each with masters and slaves. So if one is overloaded the other will pickup the slack. This gives you, not double but much better performance. This can also be done to server the website from different locations all over the world.
Just a few ideas we use in practice for our Magento clients.