I would weaken the definition of even/odd to say that a set is even if /there exists/ a way to pair things off, and odd if /there is no way/ to pair things off (ie, not even). So the countable numbers would be even.
It's also not clear to me what justification there would be for a "preference" for the "even" category that way -- it seems arbitrary. Why not be odd if there exists a way to pair things off such that one is left over, and even if there isn't such a way?
Uncountability is a particularly interesting form of non-divisibility, so I'm just fine calling all uncountable sets odd and countable sets even...
(And just because we're hung up on divisibility by two, let us remember: All prime numbers are odd, and two is the oddest of them all.)
Being "even" seems like a much more interesting (and simpler) property of a set. I don't see what use there could be to know that you could pair things off, with one element left over. When you extend the notion you do have to decide what to preserve, but to me parity is much more about divisibility and symmetry than it is about reminader. I agree that it's arbitrary, though less arbitrary than the odd definition.
But it all just seems silly. We can say the set of positive integers is even because we can come up with a pairing of elements, while the set of positive reals is odd because we can't come up with a pairing? Where's the mathematical utility in that?
And you then you could retort with sets of size four, and I could use five, and then we can argue about whether we'll end up at the limit with more odd sets or even sets, and now we're arguing in circles. Reductio ad absurdum.