"How much diagonal" a matrix is
You might consider as a first approximation:

$\sum_i((A[i,i])^2) \over \epsilon + \sum_{i \ne j}((A[i,j])^2)$

(The epsilon value is there to avoid divide-by-zero errors).

Having said that, you might also consider the question of whether the matrices are tri-diagonal. A matrix is often converted to tri-diagonal form before computing its eigenvalues.

Another measure of "diagonalness" could be the sum of the absolute value of the differences between the eigenvalues (arranged in sorted order) and the diagonals (arranged in order of largest diagonal-entry first). This is great if you already know the eigenvalues. In fact, it is probably a better measure. However, in terms of efficiency, I would probably prefer the sum of squares ratios.