Localization between Mainland China's 姑娘 and Taiwan's 小姐 In Taiwan, we call women 小姐 and this is often used in everyday situations including calling for a waitress or anyone in the service industry. 

However, I have heard this is rude to call a woman a 小姐 in China because they use the negative connotation of the word 小姐. Instead, Mainlanders call a woman 姑娘. Is this the same throughout all of China, or is it different in places such as Hong Kong and Macau (which uses mostly Cantonese). If we go to a rural part of China (outside of major cities like Beijing, etc) would calling a waitress 小姐 be considered rude? Would this hold true for other semi-Chinese speaking countries (Singapore, malaysia, indonesia, etc)?
姑娘 is more used in northern China or say the mandarin spoken regions. 小姐 is more often used along the coast especially in south.

小姐 gets the meaning of sex worker in 90s. In formal situation, it's still prefrered to use 小姐 rather than 姑娘, which sounds informal and rural.