how certain is science regarding this process you describe? - Sanchy
Its a great question. I think the most honest answer would assign a slightly different certainty value to different parts of the process. The age of life on earth is really certain as is the appearance of complex cells 2 billion years later.
The event that made complex cells - eukaryotic - possible was called endosymbiosis. This was when a bacteria became engulfed by an archaea. Lynn Margulis argued for this explanation for a long time before sufficient evidence proved it was true. It was a good example of how science works. It has now moved from hypothesis to "theory" in the scientific sense of the word. Unfortunately she continued to press her ideas to argue for "serial endosymbiosis" but the field of phylogenetics has proven her to be wrong on that.
The three steps to sexual reproduction is not really controversial. Each of them are very well known features of bacterial life. The genius was explaining the advent of meiosis from mitosis as described by Tom Cavalier-Smith.
All of these ideas are subjects of many scientific papers that you could access online. Thankfully writers like Nick Lane make the technical details more accessible to the rest of us via popular science books.
What I have described is the beginning of sex without sexes. It was a relatively simple operation that involved cells swapping genomes and mixing up their genes. In a world of high mutation rates and strong selection pressures this made it possible for useful combinations to "find each other" and others to be discarded from the gene pool.
One of the challenges to sexual reproduction resulted from the presence of mitochondria. These eventually gave up more than 99% of their genome to the nucleus of the cell but retained a few critical genes to do with controlling the rate of respiration. In this way they can respond quickly to changing demands of the cell on a local level. The problem is that the two genomes must work together very precisely. Mitochondrial DNA is not recombined, it is passed on through cell division in the same way as their bacterial ancestors.
It is for this reason that two sexes are the norm in sexually reproducing species. One larger gamete also includes the mitochondria while the other smaller more motile gamete contains just nuclear DNA. The former is by definition female and the latter male.
All the features of sex in multicellular organisms such as genitalia are much later inventions of evolution by gradual Darwinian evolution. Many of these stages of development can be observed in extant species. Consider the difference between mammalian sex and external fertilisation as practised by fish for example.
In modern complex multicellular beings like us most female gametes fail the test of the ability of the mitochondria to sync with nuclear genes for respiration. Female embryos have about 7 million oocytes by the fifth month of development. This number has reduced to around 2 million by birth. By the age of 40 there are only around 25,000 left. Only a few hundred of that original 7 million will ever mature and have a chance of reproduction. The majority of fertilised eggs spontaneously abort at a very early stage before the woman is even aware of being pregnant. It is thought that these are due to failures of cellular respiration.
Sex certainly makes successful reproduction much more difficult but far more advantageous for the cells that manage it. There are even a number of species that reproduce quickly via non-sexually but resort to sexual reproduction occasionally in response to availability of resources.