I would start by checking what your traffic load would cost under Mapbox and Bing and if they're too expensive I'd start checking some of the smaller OSM based hosts mentioned in this thread.