To start with, be sure to distinguish "seeing that much of [coworker] makes me feel uncomfortable" from "I don't think [coworker] is representing our firm well" - the first is your business, the second is not.
How about a sort of flowchart? Consider what will happen if the employee really truly objectively is dressing inappropriately for work (a bathing suit and bare feet perhaps?) or you really truly are setting a culturally inappropriate bar for "work appropriate" that no longer exists (in my first job both bare legs and open toed shoes were banned for women - pantyhose all year round thankyou) because it matters who is right and who is wrong.
If you go to HR straight away:
- if you're right, HR will know how to handle it. They might contact the employee directly or send out a general reminder of the dress code. There will be no direct conflict between you and your coworker. Chances are, their wording will be less embarrassing than yours - HR is trained on this stuff and knows how to be gentle, plus they have the advantage of saying "some people say" which is less confrontational than "I don't like" ever can be. The coworker will dress more appropriately, or leave, and either way you're happy.
- if you're wrong, HR will tell you so and you will go back to your desk and your coworker will never know you had an issue. You may not be happy but at least you know where you stand and you didn't make things worse.
If you go to the coworker directly:
- if you're right, you'll have to convince your coworker that you are - we all choose what clothes to wear to work based on what we think is ok, so there will have to be some sort of arguing and proving. It's likely to be unpleasant for either or both of you and deeply embarrassing for the coworker. You might end up with a more appropriate workplace, or you might not. It's possible that you will be objectively right but the coworker will not be persuaded and will not change anything, except being ticked off at you.
- if you're wrong, your coworker will be trying to convince you, and it's likely to have all the same issues of embarrassment and ticked-off-ness.
In both these cases, since the conversation is about appearance and modesty, the person might feel harassed due to their sex or sexuality and file a complaint. This could go very badly for you indeed, especially if your modesty rules are founded in your personal religious beliefs and someone decides you're trying to impose those in a workplace. If you are not a peer to this coworker you especially want to avoid this route.
If you go to a mutual superior of this coworker, it's sort of a cross between HR and talking directly. The boss has some of the anonymity aspects that HR has to offer, but without the skills at discussing delicate subjects. It's better than going to the coworker directly, and if you have no HR it may be your only choice.
The final option is finding some sort of same-niche coworker who meets your standards. Say the not-work-appropriate person is a 20-something woman, and there's another 20-something woman in the office whose dress habits meet your rules. You might approach that person and ask her to intervene for you. You're hoping she'll preserve your anonymity and keep the whole thing discreet, without risking any punishment for the not-work-appropriate person since you're not getting the boss or HR involved. This could work great, but choose your same-niche coworker carefully, since "You'll never guess what happened today! Old stick-in-the-mud three desks down complained to me about your shoes and asked me to have a discreet word with you about being more work-appropriate. Can you believe it?" is as likely as the delicate words of advice you were hoping for. And DO NOT find a different-niche coworker, like someone of the same gender but 30 years older, or someone of the same ethnic background but a different gender, to have your discreet word for you. That's not going to work at all. If you find this same-niche person,
- if you're objectively right, the person you approach may agree with you, and may or may not care enough to pass it on nicely. It's possible this will work as well as the HR thing.
- if you're objectively wrong, the best you can hope for this that the person you approach will tell you so. More likely they will "smile and nod" then never do anything about it. This has made things worse since now that person thinks you're a meddler and a prude and who knows what else, and may gossip about you.
I guess this is all adding up to
- go to HR if you can
- go to your boss if you can't
- don't save up months worth of irritation before you complain
- be prepared to hear that your standards are not the standards of the workplace
- do not discuss anything this personal with your coworker directly no matter how uncomfortable you feel