Sentence structure....Help

Personally I think using "holes-in-one" would be hypercorrect and that you would be trying to avoid an ambiguity that does not exist. A hole-in-one achieved by two golfers at once holding the same club at the same time would not be valid, and the reader would naturally assume the common sense meaning (namely that they each scored a separate hole-in-one). Each person separately scored a (single) hole-in-one. You could use "respectively" to make this clear:

"They were avid golfers and became the first man and first woman, respectively, to score a hole-in-one at the new course."

You could also avoid the repetition of "the first":

"They were avid golfers and became the first man and woman, respectively, to score a hole-in-one at the new course."

Why not this option: "They were avid golfers and became the first golfers to score a hole-in-one at the new course."

I read both of those sentences as conveying the same message: each person scored a hole-in-one and each was the first of that gender to do so. I don't see an ambiguity. There's more than one way to skin a cat and more than one way to effectively communicate the same idea. No need for an either-or in this case, I think.

As you specifically separate them as "the first man and the first women"
Rather than 'first man and women' I do not think the plural of holes is necessary

You do mean woman not the plural...correct? Typo?