This is more properly a comment on gowers' quotient group example, but a little long for that.
For me the canonical example of not making a choice by making all the choices is the quotient of a finite-dimensional vector space $V$ by a subspace $X$. Naively (imagine back to taking linear algebra for the first time) we might want this to again be a subspace of $V$. This is especially tempting when one has not yet been broken of the habit of thinking immediately of $V = \mathbb{R}^n$ with its extra inner product structure. With an inner product in the picture, the orthogonal complement of $X$ is a perfectly reasonable and natural quotient object.
Ignoring this extra structure, any complement $Y$ (subspace such that $X+Y=V$, $X\cap Y = 0$) can play the role of the quotient $V/X$. Such a complement comes equipped with a natural map $V\to Y$ obeying the universal mapping property. So existence is not a problem for this "definition" of quotient like it would be with groups. Every quotient map of finite dimensional vector spaces splits.
But without some extra structure lying around like an inner product on $V$, we have no natural way of choosing such a $Y$. So we instead define $V/X$ to be a set of cosets, each of which (except zero) contains one point of each possible $Y$. The resulting object is no longer a subspace of $V$, but it has the advantage of avoiding making the choices by making all the possible choices. This naturality makes the "real" definition extend to infinite dimensions, for example, without using choice.