Without writing my entire life story, here are some pointers.

Best city: Leverkusen. Easy to get appointments, incredibly friendly personnel. Honorable mention for Potsdam.

Worst city: Saarbrücken. I was undocumented a couple months because they couldn't get hold of my documents and refused to give me anything saying it wasn't my fault. They called security to bring me outside, too. When I pointed out that without documents I could be deported they laughed and said "that almost never happens".

Worst delay: Köln. They sat on my documents for two years - not because they had to, mind you, but partially because they decided to proof from scratch documents that had already been vetted by Leverkusen. In the end I had to sue them.

Most improved: Berlin. By the time I left they went from overworked to quite okay. They also used to offer a queue for those who needed an appointment right now but couldn't get one the official way.

Generally speaking big cities are a nightmare and small cities are a delight.