I think 'infinite but countable' isn't so surprising—even without a formal definition, I think most people would expect the counting numbers to be countable—but maybe the fact that there are infinitely many more rational numbers than counting numbers, and yet there are exactly as many rational numbers as counting numbers?
(This is one of many ways of phrasing it, but it perhaps understates how much bigger the rationals seem to be than the counting numbers; the description I've given would apply as well to the set of all integers, whose countability is still perhaps surprising, but not as surprising.)