Why are there two sexes?

It is not obvious why there have to be two sexes.

Sex itself is obvious: by mixing genes we increase variability.

But having two sexes rather than just being able to reproduce with anyone reduces the possible mating pool by half!