It seems intuitively wrong that you can say "All X are Y" and yet that doesn't imply "At least one X exists".

It also seems intuitively wrong that there are different sizes of infinity, yet Cantor discovered exactly that.

That's how math defined what "all" means. You can be talking about all elements of empty set without implying it must have some.

Basically it disentangled two unrelated concepts, that English language unduly mixes. Concept of every item having some quality and concepts of at least one item existing.

That how we define "all" logically but not linguistically. For instance, linguistically we would consider this inconsistent: "all 10-foot men have black hair AND all 10-foot men have blonde hair" yet it is true, logically, if there are no 10-foot tall men. The translation of the English word "all" should be something something like: |Q| > 0 ∧ ∀x∈Q, x is ...

In formal logic, but in regular English that would not be true

If that is true then liar said truth.

And that's why we must conclude that there must be a ten-foot tall man, so it can have non-brown hair, so that the liar indeed lied.

Why liar can't lie about ten-foot tall man? Liar could mean two-inch hamster but lied and said ten-foot tall man

Indeed, which is why the premise is false. So if a liar who always lies says that thing about ten foot men, ten foot men must exist, and at least one does not have brown hair.