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.