Forget about barbers -- they give rise to no paradox (there can't be a barber in the village who shaves all and only those who do not shave themselves, end of story).
We get a paradox when plausible premisses we have independent reasons to believe lead by reasoning we have independent reasons to think is compelling to a contradictory conclusion. (We have no independent reason to suppose that there is [or even can be] a village with a barber who shaves all and only those who do not shave themselves, so there's no paradox in proving there can't be one.)
So back to Russell's Paradox proper. Here the background plausible assumption is that whenever we can sensibly talk of the $F$'s (or the objects which have the property $F$) then there is a set which contains just such objects. What could be more natural, than to think that when we can pick out some things, we can talk about a totality, collection, or set, containing just those things?
Suppose the predicate $\phi$ expresses the particular property $F$. Then the claim that there is a corresponding set $\sigma$ containing just the $F$s is the claim that there is a $\sigma$ such that $\forall x(x \in \sigma \leftrightarrow \varphi(x))$. Usually this is just fine. But the plausible principle is that this is fine whatever predicate we take, expressing any property we choose. In other words, the plausible "Naive Comprehension" principle is that every instance of the schema $\exists y\forall x(x \in y \leftrightarrow \Phi(x))$ is true.
And what the argument of Russell's Paradox shows is that if you accept standard logic and allow $\Phi$ to be substituted by expressions which themselves contain $\in$, then contradiction ensues.
What to do? Revise logic? A few extremists want to! Not allow substitution of $\Phi$ by expressions which themselves contain $\in$? But that would seem not to be taking sets seriously as things that can be mentioned in defining genuine properties. So it seems we have to reject Naive Comprehension. But that's initially very puzzling (although we can learn quickly to live with it): for the idea that if we can talk about the $F$s we can talk about a collection of just those things initially seems so very natural and compelling.