Just treat people nice. There's a way to compliment a woman's dress or hair without sounding like a creep. In fact, women who are friends do it all the time. It's part of how women form platonic relationships. One of the nicest compliments you can pay someone is noticing a conscious change that they've made in themselves!
Right? I'm one of the most socially awkward people I know but even I can pull off a "hey, nice new frames!", "cool T-shirt!", or "nice new haircut!" to a female co-worker without sounding like a creep. Claiming that's impossible to do "safely" – especially from someone in a managerial role, who should know how to talk to people – is just lazy CYA behavior.
EDIT: Side note – one of the clearest (subconscious) dividing lines between "creepy" and "normal" compliments is – how much time am I spending enjoying the thing I'm complimenting? If either your comment implies "I (may) have spent time staring at you to come to this conclusion", or if your focus (eyes/body position) lingers on the person you're complimenting, it will be perceived as creepy. If neither of these is true, it won't.
Examples:
"Nice new frames!" -- noncreepy. Not specific enough to have required more than a second's glance to formulate. Speaker may not even have actually formed an opinion.
"Those pants fit you well." -- creepy. You must have been looking at my butt and thighs for at least several seconds to come to this conclusion. Better: "That's such a cheery yellow blouse!" You could see and judge the color across the office in a second's time.
"I like your haircut", followed by several seconds of silence while you continue to look at me or my haircut -- creepy. You are enjoying this aspect of my body too much. Better: "I like your haircut", followed by topic change or end of conversation.
"You look good today / I like how you look" -- creepy. It's so nonspecific that I don't know what's going through your mind. Better: "I like the new look" (if the "new look" is something obvious), or be otherwise specific.
Note that all the above applies equally across or within genders. I (male) would indeed be creeped out if a male co-worker said one of the "creepy" examples above (with the possible exception of "you look good today", only because I might have more insight into what's in his head, assuming he is heterosexual). And I cannot think of one time a male co-worker has done so.
"Thank you for helping out today - it means a lot that I can always rely on you."
"I really appreciate the energy and positivity you bring to the office - you make this a way better place to work."
You get the idea.
Last comment: it's easy to assess your own comments as non-creepy, either out of bias or because you're genuinely non-creepy. Unfortunately, that assessment is worthless, because it's how others assess your comments that matters. Nor would I ever, as the "boss", want to have try and explain to anyone working for me, especially male employees, the elaborate and highly subjective set of "rules" you've laid out here. Far easier to just not go there.
I mean, if that's how you look at putting a modicum of effort into social interaction, you've got to question whether you really value relationships with co-workers of the opposite sex at all.
