Dan Asimov writes:

P.S. I meant to mention that someone else brought up this example in math-fun some years ago.

That could have been me.

But I don't recall knowing exactly what "natural" meant in this context.

It means invariant/equivariant under a relabelling of the elements of S. The article "Producing New Bijections from Old" by David Feldman and me (published in Advances in Mathematics, volume 113 (1995), pages 1-44) goes into more detail about this. In this particular case, the upshot is: If a set S comes equipped with a specified subset T of odd cardinality (which is automatically true if S itself has odd cardinality), then there is a bijection f between the odd-cardinality and even-cardinality subsets of S that is equivariant with respect to the permutations of S that preserve T (e.g. the map that sends every subset of S to its symmetric difference with T), and conversely, if a set S comes equipped with a bijection f between the odd-cardinality and even-cardinality subsets of S, then there is a subset of S of odd cardinality that is invariant under all the permutations of S that respect f (e.g., f of the empty set). Jim Propp