First, some protists do reproduce sexually; they alternate generations between a haploid and a diploid phase.
Diploid -> meiosis -> haploid -> fusion -> diploid
As to how distinct sexes emerged, that is an anti-inbreeding adaptation; the ancestral sexually-reproducing protist most likely had only one sex. And many protists and fungi retain some of this heritage by having lookalike sexes ("isogamy").
And some organisms have more than one "mating type" or sex; ciliates can have 50 sexes and some basidiomycete fungi have thousands. Though the sexes in such multi-sex organisms usually look like.
Distinct sexes are mostly an adaptation to being multicelled. To give a new organism a head start, it is a good idea to stuff the gametes with food. But that makes them slow, and if some alternate type of gamete emerges that is lightweight and specialized for swimming, then that will reach the food-stuffed gametes more easily. Thus, some gametes become specialized for food storage (eggs) and some for traveling to the other gametes (sperm).
Something that has happened at least twice -- in animals and plants.
™ Version 4.2