What structure does the alternating group preserve? A common way to define a group is as the group of structure-preserving transformations on some structured set.  For example, the symmetric group on a set $X$ preserves no structure: or, in other words, it preserves only the structure of being a set.  When $X$ is finite, what structure can the alternating group be said to preserve?
As a way of making the question precise, is there a natural definition of a category $C$ equipped with a faithful functor to $\text{FinSet}$ such that the skeleton of the underlying groupoid of $C$ is the groupoid with objects $X_n$ such that $\text{Aut}(X_n) \simeq A_n$?  
Edit:  I've been looking for a purely combinatorial answer, but upon reflection a geometric answer might be more appropriate.  If someone can provide a convincing argument why a geometric answer is more natural than a combinatorial answer I will be happy to accept that answer (or Omar's answer).

(This is, essentially, just a «repackaging» of your answer. Still, I find this version somewhat more satisfying — at least, it avoids even mentioning total orders.)
For a finite set $X$ consider projection $\pi\colon X^2\to S^2 X$ (where $S^2 X=X^2/S_2$ is the symmetric square). To a section $s$ of the projection one can associate a polynomial $\prod\limits_{i\neq j,\,(i,j)\in\operatorname{Im}s}(x_i-x_j)$ — and since any two such products coincide up to a sign, this gives a partition of the set $\operatorname{Sec}(\pi)$ into two parts. Now, $A_X$ is the subgroup of $S_X$ preserving both elements of this partition. (I.e. the structure is choice of one of two elements of the described partition of $\operatorname{Sec}(\pi)$.)
