After some digging around, I came to a few options:
- http://www.openstreetmap.org/ offers an export function with PDF and SVG. I can export to PDF and then take screenshot to create a small image with suitable DPI. Also see http://wiki.openstreetmap.org/wiki/OSM_on_Paper for information on print maps.
- Openstreetmap labels are still small, so I've used http://maps.cloudmade.com/ with a custom style (no labels), took a large screenshot and labeled my map post export with places I needed and with suitable (for printing) font
- Use the proposal suggested by cybernard with Google API (but the copyright / terms of use question requires more research, and probably depends on the exact usage)
And I've ended up using solution #2. The whole process was not very user friendly, even with just a handful of small maps to produce, so I really hope that Apple can fix their print maps in Aperture.