I would certainly keep an eye on hosting providers that have direct access to the backbone of the internet, via their data centers and their connections. And what really is important is that you keep in mind that you might get experienced and professional support and product / services from hosting providers that are well established and known in the field. Some John Doe Hosting from 2007 overselling their services cheap, is most likely ready for a server change or even data center transfer, not to mention their servers might be full and having stability and performance issues. Whereas a hosting provider like leaseweb.com and theplanet.com are well known and have big data centers with their own racks and servers, allowing you for the right price to have proper (and not oversold) boxes with accounts, guaranteeing you good reachability online.
You can of course also plan it into your business plan to get the top5 hosting providers on board and do a 1 month dedicated hosting test on all of them. If you have an idea where your traffic is coming from, you can do ping and traceroutes from those locations to the boxes and see what the performance is under pressure. Test-drive the provider so to speak.
Good luck picking the right host, and do not forget. Pay per month or quarterly so when it's not suitable for your needs you can always transfer to another host without too much issues (money wise that is).
Let us know how it goes!