Routing
MapQuest open offers an Open Directions Service and an Open Guidance Service.
Additional information about Routing in OpenStreetMap can be found in the Routing article on the OSM wiki.
Geocoding
Cloudmade’s Web Maps API includes a geocoder. The geocoders currently used on OpenStreetMap’s main site are Nominatim and GeoNames. There is now also an open geocoding service by MapQuest.