I have posed this question to dozens of Chinese people. I think that copying their responses is against the community regulations, but I have observed several things:
女生
While this is always identified as Taiwanese it was never identified as offensive and was the best practical solution for me, because I could always point to my Taiwanese family.
姑娘
Seemed second best. Almost everyone called it provincial, but only few rejected it, claiming the Japanese used it discriminatingly. The rejectors were Notherners though. From 太原 and 北京。
美女
Many older traditional people see this as very bad Chinese, but a connection to prostitution was only once explicitly stated.
小姐
While many people defended it, this was criticised as relating to prostitutes more than any other.
These results are very different from what I thought when younger, namely: 姑娘 is the normal term and a girl might even use it talking about herself to people of equal status. 小姐 is the young miss from a noted family. 美女 is absolutely not a standard address and indicates intimate interest when used as one. I am very curious to know if this reflects the thinking before the cultural revolution, or just my world. I have created a question here:
小姐 and similar terms before the cultural revolution