My advice would be to first make a list of your requirements - can you admin the server by yourself or do you need a managed service? What kind of hardware do you need? How much bandwidth? What location, etc. Then, make a list of potential providers that can meet your needs. Contact each to make sure they respond in a manner and timeframe in which you find to be acceptable. Once you have your list narrowed down, search for reviews and see what you can find.