Does unbalancing a feistel cipher always improve security? Does it improve security at all?
Actually the article you link to does not say that a balanced Feistel cipher is less secure than an unbalanced one; it says that the security of an unbalanced Feistel cipher is more easily proven, given enough rounds.

Luby and Rackoff have shown in 1988 that a balanced Feistel scheme with only 4 rounds is "perfectly" secure as long as the round functions are "random enough". This deserves clarification: Luby and Rackoff use n-bit blocks, and their results holds up to, at least, $2^{n/4}$ queries (the attacker is allowed to submit up to that number of blocks to encrypt or decrypt to a black box which knows the key, and yet he still cannot predict the encryption or decryption of another value with non-negligible probability). Maurer and Pietrzak, and then Patarin, later showed that with more rounds, one can get as close as wanted to the $2^{n/2}$ limit (6 rounds suffice, as Patarin demonstrated). (Of course, "random enough" round functions are ideal objects whose existence is not clear; existing Feistel-based ciphers use faster functions which are certainly not "random enough", and compensate by adding more rounds.)

By making n big enough, $2^{n/2}$ is large enough to achieve sufficient security (e.g. use $n = 256$).

Morris, Rogaway and Stegers study the problem of encrypting very small blocks; thus, they cannot make $n$ "large enough". They must cope with a small $n$. The maximum theoretical security of a Feistel scheme (balanced or not) is $2^n-3$ queries (there are $2^n$ possible block values; if the attacker knows the encryption of all save two, then he can guess the remaining two with 100% accuracy, because Feistel schemes are always even permutations; this is the only known structural weakness of Feistel ciphers). The authors say quite clearly (end of page 4) that there is no known practical attack on a Feistel cipher with enough rounds, even with small blocks, so the $2^n-3$ security limit is in practice achieved. But they want more than practical security, they want proven security. A security proof works by assuming that the round functions are information-theoretically secure, and sees how the whole cipher stands up under that assumption. The trouble with a balanced Feistel cipher is that such proofs cannot go beyond $2^{n/2}$.

On the other hand, with an unbalanced cipher and many rounds (much more than 6; figures in the article go to about 64 rounds), it is possible to get a security proof close to $2^n$. This does not mean that unbalanced Feistel ciphers are "more secure", only that information-theoretic tools are more easily applied for proving security of an unbalanced Feistel cipher. And a single unbalanced round is certainly not more secure than a single balanced round; quite the opposite: security-wise, a single unbalanced round sucks. But if you accumulate enough such rounds, then you can boost the security proof to higher levels.