When is "egy" omitted? I thought it could be dropped on a sentence which expresses where something is "where can I find a car" can be translated into something without an "egy" right?
Yes, that is correct. I guess you could omit it here, as well.
Well, it kills a possible interpretation of the sentence - talking about one certain (but possibly unknown) man. It would sound more like "Where do you see (some) men?" Even the amount is unsure.
does the verb always have to follow "Hol" or can "Hol férfit látsz?" work
I can't think of a situation where the verb wouldn't have to follow "hol".