One of the weirdest Math Facts I've come across is that it's consistent with ZF minus Choice that there exists an equivalence relation ~ on ℝ with more1 equivalence classes than ℝ has elements.
This is super weird, right? Like, the equivalence classes are disjoint and non-empty, right? So getting an injection ℝ/~ → ℝ should be simple, right? For every equivalence class, just pick a represe- oh right we don't have choice.
There's a neat slide deck (Wayback Machine, sadly the original link doesn't work anymore) that goes over the intuition of just how the heck this works.
1: Because of shenanigans like this, cardinality isn't as useful in the absence of choice, so this 'more' is more about dramatic effect than technical correctness.