Something that just occurred to me as strange after working with Hilbert spaces for an embarrassingly long time:
Why is it that you can span a Hilbert space (which seems to me to have uncountably many dimensions) with a countable number of basis vectors (monomials, sinusoids of every integer frequency, etc.) Certainly, not all functions can be represented in such a way, but since the Dirac delta (boo, hiss, yes) and the unit step can, it seems like you can still disambiguate between uncountably many functions with a countably large number of numbers, which seems like something that shouldn't be possible simply as a matter of information theory.
This problem has little to do with general Hilbert spaces; the entire situation is encapsulated in just $\mathbb{R}$. $\mathbb{R}$ is uncountable but it has a countable dense subset. In fact, the problem doesn't even have anything to do with vector spaces: for any set with the cardinality of the continuum (regardless of any other structure), you can identify an element of it using countably many bits; this is just the fact that $\mathfrak{c}=|\mathcal{P}(\mathbb{N})|$.