I think there are two questions of interest here for evolutionary biologists. The big big big one is the existence of sex at all. (Here I mean sexual reproduction, involving gametes and genetic recombination.) There are fascinating lengthy discussions of the advantages and disadvantages of sex (the Wikipedia article is pretty good). The Red Queen Hypothesis is one major influence on thinking about the evolution of sex and it’s worth reading about. But most of these important ideas deal with how sex works in a population, and not with the molecular nuts and bolts of the process itself. I don’t know what the current ideas are there, but I do know that the process is very ancient–even yeast have mating. So, sex has its origins in processes very deep in the history of eukaryotes.
The second set of questions involves the drivers and nature of sexual differences, which I think is what you mean by “complementary genders.” Topics involve sexual selection, sexual conflict, life history strategies (of the whole species), and concepts like runaway selection. All VERY interesting and under current investigation. While I think it’s safe to say that the origins of sex are obscure and unknown, the origins of sexual differences in particular species can be studied robustly. The evolutionary explanations are interesting, and often contested, but there is no overall mystery.
I haven’t read The Red Queen by Matt Ridley but it’s a popular semi-classic and worth reading. On the topic of sexual differences, a recent book that I can recommend is The Evolution of Beauty by Richard Prum. It’s not a great book; his ranting is annoying and his rambling is tiresome (did he not have an editor??) but the take-home message about sexual selection is interesting and it has a lot of explanatory power.
Good luck in your unbelief. I hope you have a good community.