This is such an interesting conversation. I do enjoy sincere, no-strings-attached compliments, but if a compliment is immediately followed up with a date request, I'm less happy about it. It seems almost like bribery, especially if the guy is too heavy-handed. Though I don't come across that situation too often, it's almost always with the guy who thinks he's begin dashing and wooing me when he really just seems silly and unnatural, especially if I've noticed him doing the same thing to other women at the bar/event.
So, my vote is that a sincere compliment that is given to a stranger because he or she made your day or because you want to make theirs is fine (so long as it isn't about their figure). However, a compliment that comes with strings attached (you want their number, you're fishing for a compliment of your own, etc) isn't quite as nice. I don't think a compliment is actually rude unless it is sarcastic or overly personal/off-color.