I decided to generate a map at a 1:10000 scale (300 dpi), and then print it at twice the resolution, to have as many details as possible (and a small but readable font size).
So here is my intermediate result: A PNG, to be printed at 600 dpi, showing much of Hamburg at a 1:20000 scale (5 cm = 1 km).
It's 650 MB large :P Take some caution trying to view it!
But… it's really fun scrolling around and seeing what I can find already! :3