I'm with WillyNilly. I often compliment women who are strangers on fabulous shoes, outfits, _____, and I have no motive other than it made me happy to compliment them and I hoped it made them happy to be complimented (FTR, I am a woman). I don't generally compliment men who are strangers, but I will compliment men I know, depending on context. I am reasonably confident that my tone and delivery make it clear I am not coming on to a colleague or church member if I say "great tie!" or "I really like the new haircut!"
I don't assume everyone who compliments me is a creep or that they want to date me - I think, again, context and delivery make all the difference. A genuine compliment is never rude, in my opinion, even if the motive is to date the person being complimented.