Using cloud hosting just because it's new might be more effort and expense than you need to go through depending on your requirements.
If it's only a small company and your site won't be getting many hits then you might be better off on a normal shared account.
You're better off posting some more information about what you intend to do with the site so people can give you better advice.
█ AdelaideHost - providing shared and VPS hosting.
█ Reliability and professionalism at prices that don't hurt your wallet!
You might want to reconsider the advice of starting with a shared hosting platform, especially for a business related web site. There are many higher end platforms, even in the Cloud where you can start for very low cost, and then use the power and technology of that the cloud delivers to scale your solution up as business/site traffic grows seamlessly. For example, Cloud Servers from the Rackspace Cloud you can get up and running for about $11-$15/month depending on bandwidth and its a single click with no migration or reconfiguration to scale your Cloud Server instance larger as needed.