For me, having come into this discussion very late indeed, it is frustrating and confusing to skim over all the points that have been raised.

I accept that "sex", in particular in the context of "gender", referring largely to maleness, femaleness and the like, is such a pervasive concept in recent times (say, the last 600 million years or so) that it is easy to get it out of perspective.

To me, not counting my personal life as a mammal (of masculine gender and leanings) the biological concept of sex amounts to an elaboration on the basic concept of genetic interchange and recombination.
Now that concept, not that the fossil record offers as much detail, mostly some admittedly very impressive work on stromatolites in (by terrestrial standards) really old rocks (some 3 billion years plus) goes back, not merely to before the advent of mammals or for that matter fish, or even chordates, but perhaps even before the existence of well-organised cells as we know them today.
It seems likely that the first development along these lines was the ability to reproduce in some manner resembling what we now call mitosis. In other words the genetic material would have been duplicated, after which the cell would split. Primitive or defective early mechanisms could permit a partial reversal of the procedure, in which cells adhering to each other could unite and exchange genetic material.
Now, the only fundamental aspect of sex remaining to develop after that point, is an asymmetry between the two participants in the process. Everything else is icing on the cake.

Sometimes very pleasurable icing of course, and often downright baroque,

but fundamentally superficial all the same. To see how superficial, simply consult textbooks on elementary biology, particularly microbiology, for examples of say, the reproduction of fungi, algae and similar organisms in which some classes of gametes accumulate material supplies such as food stores, and either stay home with Mama, or drift off comparatively passively whereas others specialise in transport and take only the bare minimum of supplies, plus propulsive mechanisms such as cilia.

Careful consideration of these aspects can be very useful in developing insights into the principles.
As organisms became more complex, particularly in their bodily organisation into metazoa or metaphyta, the dizzying radiation into thousands and thousands of reproductive strategies occurred and re-occurred time and time again down the ages. They included such things as gender specialisation in many forms. For example, would you believe, all the girls I know have bigger nipples and breasts than almost all the boys I know.:!) :!)
I do not disparage the study of the function and evolution of gender and sex in macro organisms, but to do so other than in the context of the early history of sexual reproduction simply invites the kind of confusion implicit in many of the exchanges in this thread so far.
Cheers,
Jon