You could start with a reseller account from a good webhost and go from there. As you get more clients you can go from reseller-VPS-Dedicated-Colocation.
It will be hard to get clients in the beginning. Setup billing/helpdesk software as well as a decent looking website. Do not get a template from templatemonster.com as too many exist already and you will simply look like everyone else.
In addition, make sure to get your company licensed. There are many other factors however this will just help to get you move.