I have trouble intuitively understanding why a certain graph belongs to a parametarization in a certain number of parameters.
When I ask myself why the graph of the function $f(x) = y$ is a curve, it's because if it were a surface it would fail the vertical line test (for any one input there would need to be multiple outputs).
Also, the graph of $f(x, y) = z$ is a surface and not a volume because for any 2 inputs there would need to be multiple outputs.
I can't seem to develop that kind of intuition for parametarizations though. Why is the graph of $\vec{r}(t) = (x(t), y(t), z(t))$ a curve, and the graph of $\vec{r}(u, v) = (x(u, v), y(u, v), z(u, v))$ a surface?
Is there more advanced math involved behind the curtain that prevents the intuition?
What your intuition is very good! You have started feeling what manifolds are!
Manifolds are how we make mathematicaly rigorous the ideas behind curves, surfaces and higher dimensional analogues.
One way to get start you wondering about this stuff is what we call dimension of a set. One naive way is to say that if a set can be parametrized by $n$ variables then it should be of dimension $n$. But this leads to problems as for example the square can be parametrized by $2$ variables trivially but also by $1$ (as Peano's space filling curve demonstrates).
To fix that we ask that every point of the set should have a neighbourhoud homeomorphic (="looks like") some $\mathbb{R^n}.$ What we would call a line or curve cant look localy like any $\mathbb{R^n}$ for $n\geq 2$ since removing a point from a curve breaks it into 2 pieces while any of the higher spaces still remain connected. In fact Brower's famous theorem states that the notion of dimension is good , meaning that $\mathbb{R^n}$ can't be the same as $\mathbb{R^m}$.
The study of manifolds can be motivated by the implicit function theorem which states that localy the level set of a smooth function on a regular value is a graph.
There are many introductory texts about what manifolds are and what we can do with them. I suggest 4: