What one person absolutely loves, and is a 'make my day' sort of moment, to another is going to make them very uncomfortable. I think it's usually best to err on the side of caution, which doesn't mean never complimenting anyone, ever, but being aware of context, cues and so on. And also, not expecting a response.
It's safer to go with something like clothing or hairstyle rather than physical attribute, though attributes in a context like WillyNilly describes is a bit different. A middle aged guy making an appearance related comment to a teenage girl? Just don't go there. Maybe it's unfair, but it's never necessary and often comes off as awkward or creepy.
People talk a lot about how everything is so politically correct and people are so worried about offending someone. But guys still have no problem making really inappropriate comments to women in situations like, oh, being alone in an elevator.