See my preceeding to CTOCS.
Then you’ve got the whole mechanism to deliver the sperm, the tubing, blood supply, stimulant mechanism, and the ejaculatory musculature.
Then, in the same generational sequence and locale, you’ve got to explain how the female system showed up on the scene with all of its hormones, tubing, sperm-receiving hardware, nerves, ovaries, eggs, genes, blood supply, and the knowledge to use the package in concert with the male.
See also my preceding. None of these changes need to have been concomitant. These would have been very simple animals, maybe even pre-animals. The only thing that happened, at first, was that they went from releasing undifferentiated gametes to releasing dimorphic gametes. This initial innovation allowed many other innovation to follow.
But, really, even this was just a new way of doing what had been done before, even by singled celled eukaryotes. At least I think it's the case (although I'm no expert) that some protists create haploid cells which are sexually "typed" in some fashion that they can only fuse with opposite types. In practice the same as eggs and sperm, although it's a different mechanism.
The other day, I was using E. coli for an experiment, and I was explaining to my research colleague (a gynecologist) that the cells we were using are male. Male bacteria make "sex pili" which they use to puncture the female bacteria and insert DNA. If the inserted DNA contains all the genes for the sex pili, the donor becomes female and the recipient becomes male. Yeast are not classified as male or female, but as "alpha" and "A" mating types. They mate by fusing into diploid cells, although S. cerevisiae (bread/beer and also lab yeast) seem to have a preference for the haploid state.
To make a long story short, sexual reproduction seems to have been around pre-multicellular organisms.