Here are some SEO tips that we've used, and I have personally used in the past:
1) Build backlinks - Backlinks are the backbone to Google. PageRank has been devised by making one link to a website like a credit to them. Backlinks also have quality, so don't try to get spammers to link (it won't help at all), but do try to get high quality, relevant blogs to link to you because you have something to offer.
2) Use HTML tags to win. Start with the <title>, meta data, and <h1> tags. They mean the most. Also, the smaller your title is, the more the words in the title weigh. Example: If 2 sites have the same everything but H1, and a user searched for "High Quality Website Hosting Provider", one site titled "High Quality Website Hosting" would rank over one like "ExampleHost | Unlimited Bandwidth | Great Support | Free Domain | High Quality Web Hosting".
3) Use Alt-tags. Alt tags are important because they can be used to describe your image. You may have pictures of your servers, so make sure you use an alt tag to let the search engines know what it is (although google has become increasingly good without them).
4) Become a published expert in your field. Write about web hosting problems, solutions, new things you find, cool sites clients are making, etc. Just don't give your blog posts a promotional slant. People find it extremely hard to read and it reminds them of the 1 long page type of sites where they sell you an eBook or tickets to a conference where you can find the information they present just by googling it.
5) Have clients publish testimonials, reviews, and their thoughts on your service. If they're bad, reply to the review going out of your way to fix the situation. I've found clients to be extremely forgiving when I get involved. It's a free backlink and a free way to get legitimate thoughts and buzz out there about your company.
It's a lot of work, yes, but it will pay off when you find random people signing up for your service.
Also: Build reputation on Twitter, Facebook, and web hosting forums. People don't only look at search engines, so it's important to remember that a bad Google ranking doesn't mean that you're destined for failure; PageRank grows over time.