As gaming servers usually are very resource intensive (even when set up properly) a dedicated server hosting solution is probably your best bet. The main aspects to consider when looking for a new host include the hardware they offer (ram/cpu), their link speed, the amount of bandwidth offered, where they are located (for latency), and of course, how they fit into your budget. While it is very difficult to gauge reliability without first having been a customer, searching the internet for reviews is a potential way to discover any reputation issues your potential host may have. While one site with one review may not be very informative, cross referencing multiple reviews over multiple review sites should be reasonably accurate.