I'm no OpenStreetMap expert (yet), so maybe a CloudMade Mapbox comparison isn't entirely fair.
It's tough to compare the two - each has services that the other doesn't (aerial imagery, routing, geocoding, etc.) so you might end up with an implementation that cobbles together things from both.
* 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.)
They didn't answer me when I asked the reasoning behind this restriction, out of curiosity.
Since then, I use MapQuest Open and no problem so far.
As to "custom hosted tiles", yes, but you can always download the entire current OSM database, or any selected subset, and generate your own tiles by converting from the original vector data. There are a number of programs designed to do this for you.
There are hardly any services like what MapBox and CloudMade have. The closest seem to be the various consultancies that will design and host a map for you.
Having used the OSM data to generate our own tiles. It takes a lot of time and resource to manage them well (let alone updating the OSM data)
I understand it must be tough to provide such a service at low cost. Hopefully something will come up from the ashes.