小姐 and similar terms before the cultural revolution
Basically I think you are right, but it's a pretty complicated story. There is more than one use of 小姐, including title, term of address, and general noun. I think most of the discussion, including your comments, has been about the general noun, so I'll limit myself to that.

Historically, 小姐 could indeed mean 娼妓、歌女. This use goes back to at least the Song dynasty, according to the 教育部國語辭典  I have no idea if this use still exists. If it does, I'm willing to bet it's very limited.

As you say, 小姐 can also be a rich family's daughter. This goes back at least to the Ming dynasty (教育部國語辭典 again). It is still very common, I'm sure. 

This obviously can have some negative connotations. I don't know how long ago this started, but it's not recent; for example, in 茅盾's 1926 novel  幻灭, there is this sentence: 

她和王、赵二女士本是一月二日就到了汉口的。那时，她自觉满身是勇气，满眼是希望。她准备洗去娇养的小姐习惯，投身最革命的工作。 

So here 女士 is the general noun, 小姐 is little miss rich, and 娇养 is of course not good. I'm sure 小姐 here is not a prostitute!!

You prefer 姑娘 as a general noun for a young woman, yes? But 姑娘 does not appear in 茅盾's book. Instead he uses 女士. My father-in-law was like you; he used 姑娘, and he was from 山東. It may be a northern thing.

A note about Taiwan, which other people seemed uncertain about. In Taiwan, 小姐 is the standard form of address to a woman, young or even middle-aged, when you don't know her name.  You talk to the waitress, the bank teller, the woman who answers the phone, anyone who you don't know her name or status, and this is the word; it is the female equivalent of 先生 in ordinary conversation. It is the only polite general noun I know of.  

You said 美女 doesn't work for you. Same thing in Taiwan: 美女 is a beautiful woman; a looker, a knockout.  If you call a woman 美女, you'd better know her pretty well.