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.