Whence the sexes?

My take is that it boils down to increasing the probability of fertilization, primarily in our early eukaryotic ancestors, in which sexual reproduction first evolved.

On the level of gametes (the reproductive cells), it's about the difference between isogamy (gametes being the same) and anisogamy (involving a larger and a smaller gamete, which are then by definition are the female egg cell and male sperm cell). The egg cells provide almost everything the eventual zygote needs to develop, while the main role of the sperm cell is to transport a set of genes to an egg cell. As it turns out, the sperm cell can do this with much less volume, and therefore, it is more cost-effective to produce them as small as possible, but in much higher numbers compared to egg cells. Making them smaller also makes them more mobile. Both high numbers and mobility help increase the chance of fertilization, especially in species with external fertilization, as the first animals would have been. When the fertilization is done externally, the animals don't exactly "bear" offspring, so there is no tradeoff in that regard.

Once there was a distinction between the gametes, other adaptations would have made sense, such as specialised organs for the deployment of eggs/sperm and traits that allow potential mates to recognize each other. The same goes for increasingly complex behaviour to ensure that those eggs and sperm are deposited in the right place at the right time and that the offspring develops well (including courtship displays, competition, nesting, brooding, etc.), much of which is sex-specific. Of course, in some animals this ultimately led to internal fertilization, where the benefits of anisogamy are not so relevant anymore, but the animals in question would have relied on a variety of sex-specific adaptations to even get to that point, and evolution only marches forward. The existence of some species that are hermaphroditic now certainly proves that it is possible to evolve in that direction, but as you say, there are surely various hurdles with fixating such a state on a large scale.

C. elegans, one of the simplest known animals, has hermaphrodites and males, with hermaphrodites massively outnumbering the males.

Perhaps being male is a strategy to make others bear your offspring, while you don't have to, and after a certain proportion of males in the population emerges, you might as well be female instead of hermaphroditic?

Nick Lane's book Power, Sex, Suicide has an interesting model for this that seems pretty different from any of the ideas here. It has to do with maintaining alignment between the eukaryote genome and the mitochondrial genome, and having just one mitochondrial genome makes that problem tractable. So sexual reproduction needs a way to only inherit mitochondria from one gamete, to which sex is the solution.

At the organism level, I think sexual differentiation evolves to specialize in the interests of the different gametes. For plants, it's straightforward to implement the different specialized strategies in parallel, but for animals its much more costly (they would have to carry around parallel adapted organs, and split time executing different behaviors).

For cats, the female cat emits a mating call and multiple male toms typically hear the call and show up.  Then the toms have some kind of physical battle for dominance - with a lot of screeching you can hear - with the strongest, most aggressive tom obviously more likely to win.  The pair of cats do their business and the tom runs off, at which point the female starts round 2 of the mate competition...

This to me seems to be a stress test for robustness.  The tom has to perceive the female, navigate through non-home territory to her location, and survive a battle.  And to succeed he has to be able to do it on many nights, not just one, if he dies from wounds from the first battle his genes likely die with him.

This means the cat genes are constantly being stressed above natural environment stresses, for half the genes each iteration.  And yeah, for this to work the species has to afford failures, only a small percentage of the toms need to successfully reproduce each iteration.  Hermaphrodites don't have this 'disposable test animal' for evolution to check functionality each round.  

One thing that does not yet seem to have been mentioned is that it's unfavourable evolutionarily to have anything other than a 50/50 mix of males/females, as if there is a preponderance of one gender then if you are the opposite gender you'll tend to have more babies. Of course there are exceptions to this due to things like infanticide but on the whole it's a good approximation.

This does not explain how the first male came about of course, but it does explain how it only had to evolve once by chance and then immediately took over from there.

There are cases where artificially skewed gender balance can get corrected in a few generations:

https://www.theatlantic.com/science/archive/2016/08/the-strange-case-of-the-butterfly-and-the-male-killer/496637/

I don't have a total answer but I can make some predictions/contribute to the model:

1. The more dimorphism between sexes in a species or niche, the less we should expect to see (simultaneous) hermaphrodism, because success as either sex requires costly investment. I think you're making a mistake dismissing this because physical dominance as rare- sex via physical dominance qua physical dominance is rare, it is much more often serving as a costly signal of resource abundance, which is exactly what bird songs are doing.
2. Males are only deadweight loss if a population is producing fewer offspring than the environment can support. For a species at carrying capacity, twice as many offspring means twice the death rate. Therefor we'd expect to see hermaphrodism in k-strategists (which we don't, I'd guess because being a k-strategist already requires a number of costly investments) and in r-strategists that are frequently nearly wiped out locally, or finding new locations (I think this is true on the margin, although not overwhelmingly).

I'm surprised that the major role of sexual selection seems to be overlooked. Sexual species can speed up evolution by magnitudes of order, because the selection can happen culturally, "in the minds" (only a metaphor!). In theory, any adaptive change can happen in a single generation at once, provided that the selective behaviour is able to change unanimously. Hermaphrodites wouldn't work that well, because there is no clear distinction between the group that you are competing with and the group you are competing for, which would probably make any behavioral strategy unstable.

I just spotted this paper, which is a little confusing but seems to be arguing that sex can be easily worthwhile when individuals can switch what sex they are in response to their environment. That seems basically equivalent to hermaphroditism, so in some sense it's just a restatement of the question I posed above, with more math.

Huh. I like you spelling out the puzzle. I had the seed of a partial answer but hadn't noticed how incomplete it was before.

My guess had been that male expendability was a major evolutionary advantage. The fact that males can still have offspring after dying (because they already impregnated a female) means the evolutionary costs of deadly risk-taking drop by quite a bit. It also removes a lot of politics when it comes time to decide who has to risk death to protect the community from some threat. (If everyone's a hermaphrodite, it becomes a status thing. But if you have males, you obviously bias heavily toward risking losing males. Hence "Women and children first!")

I hadn't thought about it before, but it does seem to explain the animal/plant difference. This risk-taking thing isn't an advantage for plants. But it's super important for things that move and explore.

But I don't know how this would have first arisen.

I'm remembering some tickle of a claim that supposedly the human Y chromosome is a mutated X. That being male is a mutation and the default is female. I don't actually know what that would mean since human females would also have to have mutated (since they can't impregnate each other). But if there's a sensible interpretation, that strikes me as probably relevant to this question.

This exact question is discussed in Matt Ridleys The Red Queen. He puts forward that it's better for evolution in more unpredictable environments where variation becomes an advantage and vice versa for stable environments. It's a great book I'd recommend it.

The main thesis of the book is that because every other member of the species is evolving through generations you have to evolve at some rate even to stay still relative to other beings

There's a chapter on the evolution of sexes in Nick Lane's The Vital Question ("Sex and the origin of death"). It explores the benefits and costs of sex.
If I recall the big benefit of sex is gene shuffling (allows for recombinations, ie. faster experiments). Also it apparently evolved very early (didn't need much new machinery, benefits significant).