I would also take a look at CloudMade's developer tools. They offer a beautifully styled OSM base map service, an OpenLayers plugin, and even their own light-weight, very fast JavaScript mapping client. They also host their own routing service, which you mentioned as a possible requirement. They have great documentation and examples.