I think actually etiquette aside, if a person is trying to meet another person to develop a relationship of any sort (romantic, friendly, whatever) once one gets over the rules of the forum you are in (no talking during theater, don't hit on your boss/employees, etc) if its your natural impulse to compliment - do so. Because while a good first impression is important, more important - most important IMO - when developing a new relationship is to present your honest self. And if your honest self is the kind of person who compliments others, then its important to let that be known to the person you are speaking with.
I think the rudeness part would come from not taking a refusal to receive compliments. So Reason, as its your nature to do so, go ahead and compliment people/women/children/the elderly as it fits within your natural personality. But if the person you are complimenting does not take it graciously and warmly (a smile, a sincere thank you, etc) but rather coldly (a rebuff, a "humpf!", looking away, etc) don't compliment then again and realize you have different personality styles.
Likewise to anyone else - if someone compliments you and you don't care for it, make it known you don't care for it. But somewhere inside you be happy they did compliment you if for no other reason then to know "whoo-hoo this person presented their honest self to me and I now know I don't care for their personal style and I don't need to waste my time on them now."