Hi,
Since you asked, I must assume you are not a fortune 100 company looking for a tax deduction....
For most businesses, start up or not, you are going to want a host that you can trust with your business.
Your business is your livelyhood, and you depend on it being there tomorrow.
Breaking into the web should not be a scary thought. You should trust a company that has been around for more then a year, look for two or three, then price shop between them.
For a personal site, I would have less restrictions, but this is your business. I am sure you like sleeping at night. And it doesn't have to cost a fortune either.
Look around for what you need, and then look at how long they have been around. When you come up with 3 to 6, then look at your options, ask them a few questions, and go from there.
Trust your instinct after you email them with your questions.
Best of luck,
Tim L