Beijing are the beat city to learn Mandarin, cause the non-beijing locals is more than 60%. If we involved the people who are not born in Beijing but get a residence registration certificate of Beijing, the this proportion is much bigger. When u are in beijing, everybody is talking with each other using mandarin, cause it is the only way they can understand each other. But the cost and the air quality are...ah...u know.

You've been given plenty of good advice. I definitely would avoid Harbin though, never heard a good thing about it. Other than they speak clearly with no dialect. In terms of living there I've heard it described as "hell on earth".

And so I guess that in the winter, hell freezes over. :-)

Chinese people in Shenzhen speak very understandable Mandarin, for the same reason Stathis mentioned.