If you have basic experience with abstract algebra, the ideas in the Yoneda lemma should be quite familiar and even intuitive; the apparent difficulty is only in recognizing them in this new presentation.
You can think of "category" as meaning the same thing as "algebraic theory in a multisorted language with only unary functions" (the objects of the category being the sorts of the language, the morphisms being the definable functions, and the equalities between (composites of) morphisms being the laws of the theory). From this perspective, a functor from C to Set is simply a model of the theory corresponding to C, and natural transformations of such functors are homomorphisms of models. The Yoneda lemma then is about free models: specifically, it says that for every sort s, the "term model" of terms with a single variable, of sort s (equivalently, definable functions with domain s) is the free model on a single generator of sort s. [It may be unfamiliar when expressed as "Nat(Hom(s, -), M) ~= M(s), naturally in M", but that is indeed all this categorical expression is saying]
The so-called co-Yoneda lemma mentioned in the other comments also has a nice interpretation from this perspective, amounting to the demonstration that every model can be specified by generators and relations.
(I wouldn't say this is The One Right Way to think about the Yoneda lemma, because it's useful to view it from many different perspectives, but this is certainly An Important One Right Way to think about the Yoneda lemma.)
