This is where English fails as the language of mathematics. “Countably infinite” IS a contradiction in the common sense of the terms. But they have a special meaning in math that allows the apparent violation of semantic logic.
It’s as natural and intuitively obvious as it can be, not contradictory at all.
What are you doing when you count something?... You’re setting up a one-to-one relationship with the thing you’re counting and the natural numbers, or with a subset of the natural numbers.
Most people have no problem understanding that, see no contradiction in it, and can immediately appreciate it for being a useful generalization of what it means to count. It’s the key for cracking the problem of “counting” the elements of an infinite set, and getting your foot in the door.