I will answer most of the bottom line questions, but not all of your individual questions.
Covariance matrix with no structure means no a prior information or assumptions, other than it is positive semi-definite (psd), which all covariance matrices must be. Structure means some kind of a priori information or assumptions about one or more entries in the covariance matrix. For example, if it is known that the covariance matrix is diagonal, or has all diagonal elements equal, or has all off-diagonal elements equal, or perhaps a bound on absolute value of correlation coefficients, etc.
Eigenvalues being spread out, given that the subject of discussion is covariance matrices, i.e., psd, means that the 2-norm condition number, which is the ratio of the largest eigenvalue to the smallest eigenvalue, is "large". The eigenvalues will be the most spread out possible if the 2-norm condition number = infinity, which happens exactly when one or more eigenvalues = 0 (presuming there is at least one positive eigenvalue), i.e., when the covariance matrix is singular, i.e, when it is psd, but not positive definite. if there is not enough (independent) data relative to the covariance matrix dimension, and in in particular if k < p, the sample covariance matrix will be singular, i.e., have at least one eigenvalue = 0, even if the actual covariance matrix is not singular, therefore, the sample covariance matrix will have eigenvalues which are too spread out, as measured by the 2-norm condition number. The authors also claim that at least in some circumstance the largest eigenvalue in the sample covariance matrix is too large - I leave that for you to verify.
All of these schemes to adjust eigenvalues relative to the eigenvalues of the sample covariance are attempts to reduce the condition number of the unbiased sample covariance matrix estimator of covariance. There are several different ways which have been suggested in various papers over the years, beginning with Stein in 1956. they may accomplish this by introducing a bias in exchange for reducing the variance, thereby perhaps improving the Mean Square Error.
To expand on Brian Borchers' answer:
Per sections 3.2 and 6.5 of "Nonlinear Shrinkage Estimation of Large-Dimensional Covariance Matrices", by Olivier Ledoit and Michael Wolf in The Annals of Statistics 2012, inverting (adjusted to be better conditioned) estimate of covariance may not yield the best estimate of its inverse, referred to as the Precision matrix, and vice versa. So, the inverse of the well-conditioned covariance matrix will be well-conditioned, but might not be the "optimal" estimate.
If X were the MLE (maximum likelihood estimate) of covariance matrix C, then by functional invariance of maximum likelihood estimation https://en.wikipedia.org/wiki/Maximum_likelihood , inv(X) would be the MLE of inv(C). In this case, X = sample covariance matrix, so inv(sample covariance matrix) is the MLE of inv(C). However, the adjustments to the MLE in order to get a better conditioned solution mean that the adjusted estimate is not the MLE of C, and therefore there is no a priori reason to believe that the inverse of the adjusted estimate of C will be the "best" estimate of inv(C). And that is the point of those sections in the referenced paper, at least with regard to the proposed estimator of C and what that means for the inverse of C.
Best Answer
What you are describing sounds to me as ridge-regression or Tikhonov regularization. You add a ridge to the diagonal, i.e. a scaled identity matrix.
The problem is that if you have more variables than observations, i.e. $p>>n$, you cannot estimate the parameters in some models, e.g. a linear model. If you have a model: $$ \mathbf{y} = \mathbf{X}\beta + \epsilon $$ Where $\mathbf{y}$ is $n\times 1$ and $\mathbf{X}$ is $n\times p$. Now the estimate of $\beta$ is of the form: $$ \hat{\beta} = (\mathbf{X}^T \mathbf{X})^{-1}\mathbf{X}^T \mathbf{y} $$
Note that the matrix $\mathbf{X}^T \mathbf{X}$ will be rank deficient if $p>>n$, (here the matrix $\sigma^2(\mathbf{X}^T \mathbf{X})^{-1}$ is the covariance matrix of the parameters $\beta$). Thus we need to add some form of regularization to be able to get a solution, because that requires us to invert this matrix. One such type is the one you mention.
So this is better, because we cannot get any estimate unless we throw away some of the variables or add some form of regularization.
EDIT: To address your question of if this estimate presented in the paper is better than the true covariance matrix you should read over the conlusions in the paper:
Thus, the estimate they provide is being compared to the sample covariance estimate. Not the true underlying covariance matrix.
EDIT2: The way the authors describe this as better, (on page 3 in the manuscript), refers to the condition number of the matrix. That means that their estimate is more numerically stable. This is usually the case when you perform any kind of regularization, since you are reducing the effective number of parameters that you are estimating.