One criterion not mentioned yet is naturality in the categorical sense, which can also be phrased as equivariance with respect to permutation actions. This approach has been extensively developed by André Joyal and others, under the name of combinatorial species.

In almost all natural examples (I’m tempted to remove the “almost”), the sets $A_n$ and $B_n$ aren’t just $\mathbb{N}$-indexed families of sets; they also come with natural permutation actions, with $\Sigma_n$ acting on $A_n$ and $B_n$. Equivalently, $A_\bullet$ and $B_\bullet$ can be seen as functors on the category $\mathrm{FinSet}_{\cong}$ of finite sets and isomorphisms; this representation is often clearest to work with. E.g. if $A_n$ is “finite trees with $n$ leaves”, one can generalise it to a functor on $\mathrm{FinSet}_{\cong}$ by taking $A_X$ to be “finite trees with leaves labelled by $X$”; an isomorphism $\varphi : X \to Y$ gives an action $A_X \to A_Y$ by relabelling leaves.

One can then require the functions $f_n$ to be natural, in the categorical sense, with respect to this functoriality. That is, for an isomorphism $\varphi : X \to Y$ of finite sets, and $a \in A_X$, one should have $f_Y(\varphi \cdot x) = \varphi \cdot (f_X a)$. In terms of permutation actions, this is equivariance: $f_n(\sigma \cdot x) = \sigma \cdot f_n(x)$.

The effect of this, roughly, is to rule out constructions that involve arbitrary or non-uniform choices at any stage. I think all examples that would traditionally be considered “natural” or “canonical” by combinatorialists are natural in this sense — I’d be very interested to see a counterexample to that. On the other hand, one can produce contrived examples that are natural in this sense without being “natural”: e.g. take some example with two different natural bijections $f$, $g$, and define a new one by using $f$ for even $n$, and $g$ for odd $n$.

Comparing to the other criteria suggested: this one is pretty much orthogonal to computational complexity. It’s a bit linked to logical constructivity: there are metatheorems saying that anything definable in certain constructive logics must be natural in this sense.

One criterion not mentioned yet is naturality in the categorical sense, which can also be phrased as equivariance with respect to permutation actions. This approach has been extensively developed by André Joyal and others, under the name of combinatorial species.

In almost all natural examples (I’m tempted to remove the “almost”), the sets $A_n$ and $B_n$ aren’t just $\mathbb{N}$-indexed families of sets; they also come with natural permutation actions, with $\Sigma_n$ acting on $A_n$ and $B_n$. Equivalently, $A_\bullet$ and $B_\bullet$ can be seen as functors on the category $\mathrm{FinSet}_{\cong}$ of finite sets and isomorphisms; this representation is often clearest to work with. E.g. if $A_n$ is “finite trees with $n$ leaves”, one can generalise it to a functor on $\mathrm{FinSet}_{\cong}$ by taking $A_X$ to be “finite trees with leaves labelled by $X$”; an isomorphism $\varphi : X \to Y$ gives an action $A_X \to A_Y$ by relabelling leaves.

One can then require the functions $f_n$ to be natural, in the categorical sense, with respect to this functoriality. That is, for an isomorphism $\varphi : X \to Y$ of finite sets, and $a \in A_X$, one should have $f_Y(\varphi \cdot x) = \varphi \cdot (f_X a)$. In terms of permutation actions, this is equivariance: $f_n(\sigma \cdot x) = \sigma \cdot f_n(x)$.

The effect of this, roughly, is to rule out constructions that involve arbitrary or non-uniform choices at any stage. I think all examples that would traditionally be considered “natural” or “canonical” by combinatorialists are natural in this or some closely related sense — I’d be very interested to see a counterexample to that. On the other hand, one can produce contrived examples that are natural in this sense without being “natural”: e.g. take some example with two different natural bijections $f$, $g$, and define a new one by using $f$ for even $n$, and $g$ for odd $n$.

Comparing to the other criteria suggested: this one is pretty much orthogonal to computational complexity. It’s a bit linked to logical constructivity: there are metatheorems saying that anything definable in certain constructive logics must be natural in this sense.