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 ...