You are completely correct with your analysis of the statement "everything I say is false": it must be false, but this is not a paradox in the strict logical sense.
(Some people use the word "paradox", or even more frequently the adjective "paradoxical", more loosely, meaning anything that is true, though apparently false; or false, though apparently true. You could argue that the falsity of the above statement is not immediately obvious, so there may be a paradox in this sense.)
However, the term "Liar Paradox" is more usually applied to the statement "this statement is false", and this is a genuine paradox.
Mathematics, logicians and concomitant philosophers distinguish between explicit and implicit definitions. If you've seen plenty of mathematical definitions but haven't thought or read much about foundations, you're probably only familiar with the former. The latter is what axioms often provide. Let me explain with some examples.
What is a group? If you don't know the definition, feel free to Google it. It's a list of "group axioms". A group is anything satisfying those axioms; that's an explicit definition. Any theorem saying "all groups are like this" is provable as-is, which sounds contra Russell. (The proof might use stronger rules of inference than someone else is comfortable with, but let's assume we fix these rules so we know which theorems count. Besides, Russell doesn't seem to be talking about that subtlety anyway.)
On the other hand, what is a set? Ooh, that's harder. I can copy-paste my preferred axiomatic set theory, let's say ZFC or whatever. Then we have an explicit definition of the models of ZFC, just as the group axioms explicitly define "groups", which might be given the more long-winded label "models of group theory". (But that's probably not a useful description, since theorems talking about relationships between groups are of greater interest than theorems talking about relationships between models of ZFC, until you're doing mathematics that goes far beyond working in ZFC itself.) What we don't have, however, is an explicit definition of the sets in ZFC. We only have an implicit definition, in the form of axioms making claims about what they're like.
So, are axioms claims of the form "if X then Y" rather than just Y? I suppose you could formulate each ZFC axiom as "this holds if we're taking about sets". But even if we do, I don't think that addresses the point Russell was trying to make. His point was that if mathematics has to assume something to prove Y, but X suffices, "if X then Y" needs nothing to be proven (again, this either folds rules of inference into the claim or doesn't consider them to be a "something" we're assuming), but Y does. This usually only matters if you're either getting your head around your first X-violator, or trying to understand why any philosopher would say your favourite theorem, as you would word it without so many assumptions spelled out, isn't a tautology.
So as you see, foundations are a complex interplay of rules of inference, axioms and definitions, and the last two overlap.
Best Answer
(1) The OP writes:
No Bertrand Russell didn't say quite that. Rather he distinguished two readings of "The present King of France is not bald." This can be parsed as either "It is not the case that the-present-King-of-France-is-bald" or "The present King of France is not-bald". (There's a scope ambiguity -- does the negation take wide scope, the whole sentence, or narrow scope, the predicate?)
Russell regiments "The present King of France is bald" as
$$\exists x(KFx \land \forall y(KFy \to y = x) \land Bx)$$
where '$KF$...' expresses '... is a present King of France' and '$B$...' expresses is bald (there is one and only one King of France and he is bald). Then the two readings of "The present King of France is not bald" are respectively
$$\neg\exists x(KFx \land \forall y(KFy \to y = x) \land Bx)$$
$$\exists x(KFx \land \forall y(KFy \to y = x) \land \neg Bx)$$
The first is true, the second false -- no paradox or contradiction. Trouble only arises if you muddle the two.
(2) The OP also writes
Compare: "The (present) King of France" is a meaningful expression -- you know perfectly well what condition someone would have to satisfy to be its denotation. In fact, it is because you understand the expression (grasp its meaning) that -- putting that together with your knowledge of France's current constitutional arrangements -- you know it lacks a referent. The expression is linguistically meaningful but happens to denote nothing (with the world as it is). Similarly there's a good sense in which do you understand "$\frac{1}{0}$" perfectly well: it means "the result of dividing one by zero". It is because you understand the notation, and because you know that division is a partial function and returns no value when the second argument is zero, that you know that "$\frac{1}{0}=3$" isn't true. The symbols aren't mere garbage -- you know what function you are supposed to be applying to which arguments. So, in a good sense, the symbols "$\frac{1}{0}$" are meaningful even though they fail to denote a value. In Frege's terms, the expression has sense but lacks a reference.
(3) Marc van Leeuwen writes
Not so. For example, the sentence "No one is the present King of France" is not only meaningful but true -- so it can't be that just containing the non-referring "the present King of France" makes for meaninglessness.