Your example of listing a job in Men's Health but not Cosmopolitan seems good. Technically not a perfect analogue as a woman always could buy Men's Health, but in practice very similar.
Spinning off into a different angle, what if an advertiser gets the most qualified female applicants advertising through LinkedIn, and the most qualified male applicants through Facebook? (Again assuming pay per view) Is it wrong for them to target women & men on separate platforms with separate ads? Utterly hypothetical of course.
Or yet a different angle, what if they have ad "A" and ad "B", each subtly designed to excite one of the sexes. Perhaps an ad for the Marines, one emphasizing toughness & grit, the other emphasizing teamwork & "stronger together". Target one at men, one at women. Legal?
To me it seems to come down to the overall behavior of the employer, not Facebook or any one ad.