Let me answer your question as best I can; but I'll start by correcting a misconception in your question.
It actually never happens that "all units are powers of just one unit" except when the unit group is finite. The reason this happens is because $-1$ gets in the way! Suppose there's a unit $u$ such that every other unit $v$ can be written as $u^n$ for some $n \in \mathbf{Z}$. But $v = -1$ is a perfectly good unit, so we must be able to write $u^n = -1$; so this equation forces $u$ to be a root of unity, and in particular it can't generate an infinite group.
When the unit group is infinite, the best we can hope for is that there is a unit $u$ such that every unit $v$ is $u^n z$ where $z$ is a root of unity. This is precisely what happens for real quadratic fields: the fundamental unit $u$ has the property that every unit is $\pm u^n$ for some $n \in \mathbf{Z}$ (and you can't get rid of the $\pm 1$ there).
When $K$ has bigger degree you need more than one unit, and Dirichlet's unit theorem gives a precise formula for how many units you need. If the number field $K$ is generated by a single algebraic number $\theta$, then you look at the minimal polynomial of $\theta$ and count how many real and non-real roots it has: it will have $r$ real roots and $s$ conjugate pairs of non-real roots, for some $r$ and $s$. Dirichlet's theorem says that the smallest collection of units you need to get within a root of unity of every unit in $K$ is of size $r + s - 1$.
For instance, I'm particularly fond of the field $K = \mathbf{Q}(\sqrt[3]{2})$. The minimal polynomial of $\sqrt[3]{2}$ is $X^3 - 2$ which has one real root and two conjugate non-real roots; so in this case one unit suffices and the field $K$ does have a fundamental unit, which turns out to be $\sqrt[3]{2} - 1$.
On the other hand, the field $L = \mathbf{Q}(\sqrt[4]{2})$ corresponds to $X^4 - 2$, which has two real roots and one pair of conjugate roots; so we'll need $2 + 1 - 1 = 2$ units to generate everything -- there's no "fundamental unit" for $L$. There are computer programs for calculating in number fields, and my computer took approximately 0.07 seconds to tell me that if we take $u_1 = \sqrt[4]{2} + 1$ and $u_2 = \sqrt{2} - 1$ then every unit of $L$ is of the form $\pm u_1^a u_2^b$ for some $a, b \in \mathbf{Z}$.
PS: I will try and answer your updated questions.
You ask whether it wouldn't be better to take $\{ \sqrt[4]{2} + 1, \sqrt[4]{2} - 1\}$ rather than $\{ \sqrt[4]{2} + 1, \sqrt{2} - 1\}$ as "fundamental units". This is entirely a matter of taste: there's no really 'best' set to take, and lots of sets will work equally well. When $r + s -1$ is 1, then a fundamental $u$ will be unique up to replacing $u$ with $\omega \cdot u^{\pm 1}$ for $\omega$ one of the finite set of roots of unity in the field (usually just $\pm 1$); but as soon as you step to larger degrees there'll be an infinite amount of choice and it is a rather fruitless exercise to try and single out any one choice which is 'best'.
As for actually computing units in practice: the bible for such computations is Henri Cohen's book "A Course in Computational Algebraic Number Theory".
