Ask HN: Alternatives to Google's Static Maps API?

We're building a web application that needs to display many small static map images with a custom image marker in the center. Each image is around 200 x 60 pixels.

We quickly hit Google's Static Maps API limits, and their enterprise pricing is impossible for us right now.

We could use open data like OpenStreetMap with custom styles and host it ourselves. Does anyone have any experience with that for static maps? What tools do you recommend? Any other suggestions?