What is the best evolutionary explanation for the existence of 2 sexes?

In hindsight, it isn’t that hard to see the benefit of 2 sexes. Even bacteria have an archaic way to recombine genes. Genetic recombination is necessary to weed out bad mutations and makes it possible for beneficial mutations arising in different individuals to end up in the same individual. However, it is not obvious how such a system can arise through the process of natural selection. Natural selection cannot plan ahead, only what is immediately beneficial can be selected for. An organism that can reproduce asexually will be able to pass on more of its genes than one that only passes on half, therefore we should expect that species should tend to lose the capacity for sexual reproduction as its benefits are long term and natural selection cannot plan ahead.
Another problem is that if we are to have genetic recombination, then why are there only 2 sexes? If a mutation arose that allowed an individual to mate with either male or female, wouldn’t such a trait be favored by natural selection since such an individual would have access to twice the mates? Overtime, this third sex would dominate; it is interesting that such a system is not widespread.
I was fascinated by Nick Lane ideas on these issues in his book Power, Sex and Suicide. Mitochondria have their own genomes and are passed on only through the maternal line. Over time, genes from the mitochondrial genome have migrated to the nucleus but no eukaryote has lost all of them. There are a core set that are always retained in the mitochondria. Lane explains that this is because local regulation of energy production on the mitochondria is very important. The micromanagement of the production of energy in each mitochondrion from the nucleus would be an extremely complex mechanism that perhaps could not evolve step by step by natural selection and that is why we don’t see it. So, like it or not, we are stuck with a separate mitochondrial genome. As such, we need a mechanism to pass on the mitochondria. That is where the 2 sexes come in. We need to have a specialized sex that is in charge of passing on the mitochondria. There are elaborate mechanisms in place in many different species to make sure that male mitochondria do not make it into the offspring. This implies that there are good reasons why the mitochondria from both parents can’t mix. Some diseases can be traced to events where these mechanisms fail and an individual has a mix from both parents. Lane believes that the mitochondrial genome has to match up with the genes that are in the nucleus. It is easier for these to match up if all of the mitochondria are the same. Regardless of the reasons, mitochondria coming from 1 parent seems to be very important. According to Lane, regardless of any benefits we may see in hindsight, without the need for a specialized sex for passing on the mitochondria, there would be no mechanism for maintaining the 2 sex paradigm we see with only rare exceptions across all eukaryotes.