Mandarin is the winner on that front. It's the lingua franca everywhere in China sans Hong Kong, although a lot/most people in some areas speak it only as a second/third language.
Same in Taiwan, and even in Singapore I've had fun speaking Mandarin with random hawkers. Taiwan is a great place to learn Chinese without having to mess with the Great Firewall and all that :)
