Which is the right order 您好，大姐 or 大姐, 您好? A while ago I ran into a friend of a friend on the street I said 您好，大姐. (She is two year older than me, 28). She gave me a strange look like she was taken back by what I said so I was wondering: Should have I said 大姐， 您好 instead?

I am not really sure how to order greetings properly.
Age/gender nuances aside, either is fine. I'd like to point the context you worded you greeting it what got you those looks. You're in part mixing formalities with colloquialism.

Because you are merely an acquaince, calling her 大姐 can be a bit too personal. unless the person you are greeting is in the business heading a gang or mafia (which you might be a member). It's a bit like saying to a person you've just been introduced to as "Pleased to meet you, big sis." This can come off as being overly friendly or as if you are pleading for something by lowering your stature to them (like in a gang).

In my opinion, the true difference between {Greeting} + {Subject} and {Subject} + {Greeting} is what you wish to invoke/acknowledge first. If you want to acknowledge a person you would say their name first, and then follow with a greet. This will come off as being more personal (or overly polite; mockingly). However, if I wanted to emphasize the greeting as if I was pleased/happy to meet them as a person, I would use the greeting first. Think of it as if you forgot the name of the person and still wanted to greet them properly. Of course, this may vary by the region, dialect, and personal preference (of both parties), but you can still use as a starting point.

If you were better acquainted with this 女士 (used like "Ms."), such as if they are you senior in some capacity that you spend sometime with, it might be alright as a sign or respect or as a joke, but it's rarely alright otherwise. If I were to go up to you (haven't just met) and said "heeeey, big bro (大哥), wassup?" How would you feel?

If you wanted to address an audience of your peers you can address them (i.e. asking for a request) as "大哥大姐们." By doing so you would be humbling yourself, making usage in this context appropriate.

To be safe, if you've just recently met them, leaving off the title is fine.

While 小姐 can be acceptable, it's best to avoid using it in mainland China as it can be inferred as a slang term for "prostitute" or a title addressing wait staff (amongst other things), by means of tonal inflections or other indications.