Just started using OpenStreetMap on the weekend. I found Mapbox[1] to be very easy to get started with. Their plans also seem to specifically benefit the 'small user' (I.e., free developer account). At the same time I have to assume they serve big customers well too, since Foursquare is listed as a customer.
I'm no OpenStreetMap expert (yet), so maybe a CloudMade Mapbox comparison isn't entirely fair.