* MapBox: need no introduction, easily the biggest and slickest OSM-powered operation out there. Some really great technology, smart guys (they've hired a lot of the brightest stars of OSM), and a bigger commitment to "giving back to OSM" than CloudMade had. Wide range of plans from free to "Enterprise". http://mapbox.com/
* Thunderforest do a range of attractive specialist cartographies, of which OpenCycleMap is the best known, and can design and host styles to order. http://thunderforest.com/
* Set up your own server: reasonably easy for anyone with a little Unix experience, runs fine on a €59/month Hetzner box. Docs at http://switch2osm.org/ (disclaimer: my site)
* And for the client-side library, pretty much everyone uses Leaflet now: http://leafletjs.com/
* MapQuest Open run an instance of Nominatim, the standard OSM geocoder, again with high availability and generous ToUs. Setting up your own Nominatim instance isn't trivial, so use MapQuest's unless you have a really good reason not to.
* Mapbox has a basic geocoding API that comes as part of their plans.
* OSRM is the standard router, capable of blisteringly fast results which facilitate Google-style draggable routes. Source and public instance at http://project-osrm.org/ . Be aware that building the routing graph for the whole world takes a lot of RAM (though you can EC2 it if you like). The author, Dennis Luxen, has been hired by MapBox whose Directions product is expected imminently.
* MapQuest Open also offers routing, slower than OSRM but a nice free public instance.
* GraphHopper is gaining some traction for lower memory requirements than OSRM, though also fewer features. Java. http://graphhopper.com/
All-round OSM shops:
* Geofabrik are very much at the heart of the OSM ecosystem - pretty much everyone has downloaded their invaluable data extracts at one time or another. Hugely knowledgeable, helpful and capable of pretty much anything you can throw at them. http://www.geofabrik.de/
* Gravitystorm, the OSM consultancy side of Thunderforest: http://www.gravitystorm.co.uk/
(And a personal note: I do cartography (but not hosting), plus general OSM knowledge with expertise in editors and in routing inter alia. Link in the profile as per usual.)