Leipzig (about 200km south-west of Berlin) is also quite hot with startups right now from what I've heard. Cost of living is (afaik) lower than in Berlin or Munich, and the city is pretty nice to look at (lots of green, and the city center has been restored to former glory after the Wall fell). As an added bonus, it's quite central within Germany and well-connected traffic-wise, so you can get to any other place in Germany within 5 hours max.
I have to confirm that. we see quite a volume on company formations in Leipzig. Also the city has a nice vibe, is well connected, and has pretty good universities. Especially the HHL spins of some startups.