There is no good time to communicate verbally that you are not flirting with them. However, from the start you should use your paraverbal, nonverbal, and situational to communicate that you are not flirting with them.
Paraverbal
It is important to remember that communicating is not limited to what you say, but how you say it. Take the following sentence:
Hey, how are you doing?
It can be said in such a way as a simple greeting, emphasized for flirtation, or emphasized for deep concern. Depending on how you are talking, it could drastically change how it is interpreted.
Nonverbal
Posture, hand position, facial expressions, and body language all communicate various things. If you want to know what various hand positions and facial expressions are communicating there are sites with whole pages on them: Read Body Language Signs and Gestures Here is a summary of the section on hand positions (note the last one):
hands folded shows negativity, skepticism, blocking the message he receives, the other person is perceived as a stranger, defensive position (person defends his heart).
if you put your hands on your hip they widen body, you seem bigger, more threatening and convincing or influential.
hands behind your back or in front, one holding the other by the forearm denote insecurity, mistrust, fear.
hands behind your back, one holding the other by the wrist usually comes with chin up and chest facing forward symbolizing an authoritative person, courageous.
asymmetrical shaking hands show that the person is approachable, hands with slow movements show safety, securance (those that have slower moves know that what they have to say is important that’s why they have no rush, they have all the time in the world).
steeple up hands shows dominance, leadership and steeple down allegiance, obedience.
thumb in your pocket or outside the pocket denote domination, safety, strength, sexual aggression.
playing with cylindrical objects such as cigarettes, a finger, a cocktail glass or any other signifies courtship.
Another one from the same article has to do with what your eyes are looking at:
Intimate look = between the eyes and breasts to the thighs
So if your eyes are drifting down and checking them out, before you even open your mouth, you have already caused them to form a bias on anything you do say. Think of the classic example of husband is walking with his wife and turns his head as an attractive jogger passes by in the opposite direction, and the wife then smacks him. Husband did not say a word, but the simple act of turning his head was enough.
Needless to say, a lot of little things you are doing you may not even be aware of that are causing the miscommunication. One time I had someone videotape me and a group of fellow college students giving a presentation for a class. I watched the recording later, and was absolutely shocked at the little things I had done that I was not aware of. If someone ever video tapes you at a social event try to see if you get your hands and watch it several days later, to make sure that the video is correctly capturing what you think you are doing.
Situational
One of the fastest ways to communicate to an individual that you are not flirting with them, is to have someone accompany you, preferably a significant other or someone of the same gender you are trying to talk to. People tend not to flirt in front of their significant other, and so having a boyfriend/girlfriend/spouse accompanying you will let them know that anything that might be construed as flirting is likely not the case (unless of course your significant other is giving you dirty looks, then they will absolutely assume you are flirting with them).
Final Advice
If you cannot figure out how people are coming to the conclusion that you are flirting with them, then I recommend asking a close friend (preferably a women, since you state they are primarily the ones who are thinking this) who is good at picking up on subtle things for help. Have them follow you around at social events you go to, with them keeping an eye on what you are saying and doing. Then have them report anything they picked up on as flirting.