Why is this a non-holonomic constraint?

OP's example is clever. However in physics, the constraint function $f$ is often implicitly assumed to obey various regularity conditions, e.g. differentiability, which OP's example fails. For details, see e.g. this related Phys.SE post.

No. A system with $n$ degrees of freedom is said to be under a holonomic constraint if imposition of the constraint reduces the number of degrees of freedom by $1$ , to $n-1$. Every holonomic constraint can be captured by some relation of the form $f(q_1...q_n,t)=0$, but not every constraint that can be captured in this form is necessarily holonomic. You have provided an example.

When $(x^2+y^2+z^2) = a^2$ is the constraint satisfied, transforming to spherical coordinates (where one d.o.f is explicitly $r= \sqrt{x^2+y^2+z^2}$ ) allows us to describe the motion constrained on the sphere using $\theta$ and $\phi$, ie, reduction of the number of d.o.f from $3$ to $2$. Sometimes, it may not be straightforward to find this coordinate transform ; in such cases, we automate the process of describing the resultant $n-1$ dimensional motion by using the Lagrange Multiplier method.

So, calling a constraint on a system with $n$ d.o.f holonomic implies that imposing this constraint turns the system into one with n-1 d.o.f. This is by definition (see comments below)

What you have constructed indeed has the functional form described above, but it does not describe a situation with $1$ d.o.f less. The motion is very clearly still $3$-dimensional.