What is Yoneda's Lemma a generalization of? What is Yoneda's Lemma a generalization of?
I am looking for examples that were known before category theory entered the stage resp. can be known by students before they start with category theory.
Comments are welcome why the following candidates are good or bad ones.
Further examples are welcome!
Candidate #1: Axiom of extensionality (for sets)
A set is uniquely determined/can be recovered from its elements.
Candidate #2: Dedekind completions (for posets)
A completion of a poset S is the set of its downwardly closed subsets, ordered by inclusion. S is order-embedded in this lattice by sending each element x to the ideal it generates.
Candidate #3: Stone's representation theorem (for Boolean algebras)
Every Boolean algebra B is isomorphic to the algebra of clopen subsets of its Stone space S(B).
Candidate #4: Cayley's theorem (for groups)
Every group G is isomorphic to a subgroup of the symmetric group on G.
 A: I like to view Yoneda's lemma as a generalization of the description of Galois coverings in topology. To any functor $F: C \to Set$ we can associate its category of elements $El(F)$. Its objects are pairs $(x,a)$, $a\in C$, $x\in F(a)$. A morphism $f:(x,a)\to (y,b)$ is a morphism $f_*: a \to b$, such that $F(f_*)(x) = y$. Such a category is equipped with a natural projection $Q_F : El(F) \to C$, sending $(x,a)$ to $a\in C$ and a morphism in $El(F)$ to the underlying morphism in $C$. Then it is easy to see that a natural transformation $\mu: (p;\cdot) \to F(\cdot)$ is just the same as a morphism of fibrations over $C$ $$\int \mu: El(p;\cdot) \simeq p/C \to El(F)$$
This is an example of Grothendieck's construction, applied to set-valued functors. It is itself a categorical version of the correspondence between sheaves of sets and their etale spaces in algebraic geometry.
Consider for example $Nat[(p;\cdot);(p;\cdot)]$. By Yoneda's lemma it equals to $Hom_C(p;p)$. This is exactly the fibre of $p/C$ over $C$ under the Grothendieck's construction for $(p;\cdot)$. The whole automorphism of $(p;\cdot)$ is thus determined by the image of $1:p\to p$. This reminds that an automorphism of Galois covering is uniquely defined by choosing the image of one element in the fibre, thus $$Aut(M\stackrel{p}{\to} N) = p^{-1}(x),\;x\in N$$
A morphism of Galois coverings $f:X\to Y$ with $X$ connected is likewise uniquely determined (if it exists) by choosing some element of a fibre of $Y$. If $X$ is contractible, then a morphism always exists. This means that slice categories $p/C \to C$ are actually similar to contractible fibrations. I don't know how far the analogy goes, but via the classifying space functor slice categories really map to contractible spaces, because they have initial objects.
A: for graphs
Each node in a countable graph is determined up to conjugacy by a sufficiently large neighbourhood (induced connected subgraph containing the node pointed).
A: I've always seen it as a generalization of the fact that every function on a space defines a distribution.  That is, $C^\infty(M)\subset \mathcal{D}(M)$ (don't know if that's standard, I know very little about distributions except what was covered in a first year course) generalizes to $\mathcal{C}\subset Func(C^{op},Sets)$.  And then it lets you talk about whether a functor solution is representable, like whether a distribution solution is a function, etc.
A: Tannaka duality is essentially applying Yoneda twice. So a special case of Tannaka duality that doesn't require the Yoneda lemma would be Pontryagin duality.
A: Bill Lawvere has been known to refer to it as the Cayley-Dedekind-Grothendieck-Yoneda Lemma, which is catchy but only manages to include numbers 2 and 4.  I guess I can see what you've got in mind with number 1, but number 3 (Stone) puzzles me.  What are you thinking of there?
Here's another one.  It's the Yoneda Lemma in the case of one-object categories, i.e. monoids.  Let $M$ be a monoid, and write $\tilde{M}$ for its left regular representation.  Then for any left $M$-set $X$, there's a natural bijection between elements of $X$ and maps $\tilde{M} \to X$ of $M$-sets.
I don't know how many people meet sheaves before categories, but here's another example.  Fix a topological space $X$.  For each open set $U$ we have a presheaf (of sets) $\tilde{U}$, which takes value $\{*\}$ on open subsets of $U$ and $\emptyset$ on open sets that aren't subsets of $U$.  Then for any presheaf $F$ on $X$, there's a natural bijection between elements of $F(U)$ and maps $\tilde{U} \to X$ of presheaves. 
A: The (weak) Nullstellansatz: If $A$ is a finitely generated $\mathbb{C}$-algebra, then $A$ is the zero ring if and only if $\mathrm{Hom}(A, \mathbb{C})$ is empty.
More generally, if $A$ and $B$ are finitely generated $\mathbb{C}$-algebras without nilpotents, then a map $A \to B$ is determined by the map $\mathrm{Hom}(B, \mathbb{C}) \to \mathrm{Hom}(A, \mathbb{C})$ that it induces.
