Perhaps it would be helpful to remind ourself of some of the basic properties of orthogonal bases. Let's for this purpose assume the $\{|i\rangle\}$ represents an orthogonal basis of a vector space $V$. In addition to the orthogonality condition
$$ \langle j|i\rangle=\delta_{ij} , $$
we also have the completeness condition
$$ \sum_i |i\rangle\langle i| = {\cal I} , $$
which can serve as a way to resolve the identity operator ${\cal I}$.
The important thing to realize is that this is not the only orthogonal basis that one can define for this vector space. In fact any unitary operation would convert this basis into a new basis,
$$ U|i\rangle = |m\rangle $$
and it is a simple exercise to show the this new basis will also obey similar orthogonality and completeness conditions.
Let's now consider this case of an operator that is diagonal in our initial basis. This means we can write this operator as
$$ A = \sum_i |i\rangle\lambda_i\langle i| . $$
What would happen if we convert this expression to the new basis $\{|m\rangle\}$?
To do this we operate on both sides of $A$ with the identity resolved in terms of the new basis (which we'll alternatively denote by either $|m\rangle$ or $|n\rangle$). See what happens
$$\begin{align} {\cal I}A{\cal I} &= \sum_{mni} |m\rangle\langle m|i\rangle\lambda_i\langle i|n\rangle\langle n| \\ &= \sum_{mni} |m\rangle U_{mi} \lambda_i {U^{\dagger}}_{in}\langle n| \\ &= \sum_{mn} |m\rangle B_{mn} \langle n|\,.\end{align}$$
It is hopefully clear to see that the matrix
$$ B_{mn} = \sum_i U_{mi} \lambda_i {U^{\dagger}}_{in} $$
would in general not be a diagonal matrix. In factor, the right-hand side $UDU^{\dagger}$ (where $D$ represent a diagonal matrix) is the spectral decomposition for some matrix.
This also implies that if one were to perform this process in reverse, one would be starting with a non-diagonal matrix, and then converting it to a diagonal matrix by an appropriate choice of basis. Let's see how that works. Let's assume I'm given a normal matrix $M$, expressed in some arbitrary basis $\{|a\rangle\}$. (I'm deliberately using different symbols here to avoid confusion with what we had before.) According to the spectral theorem, one can now express this as
$$ M = U D U^{\dagger} , $$
where $U$ is a unitary matrix and $D$ is a diagonal matrix. Note that $M$ is still defined in terms of the basis $\{|a\rangle\}$ in which it is not diagonal. However we can remove the unitary matrices by operating on both sides as follows
$$ U^{\dagger} M U = U^{\dagger} U D U^{\dagger} U = D . $$
Thus we end up with only the diagonal matrix. In the process we have redefined the basis in which the matrix is expressed. This redefinition comes about through the unitary matrix: $|a\rangle U = |i\rangle $ and $ U^{\dagger} \langle a| = \langle i|$. Therefore, the unitary matrix that is needed to diagonalize the matrix, also convert the basis to the special one in which the matrix becomes diagonal.
Let's look at the explicit questions:
"What does it mean for an operator to be diagonal with respect to a
basis?"
It means that in this particular basis the operator (expressed as a matrix), one has non-zero elements on the diagonal only and these elements then represent the eigenvalues of the matrix. All other elements of the matrix are zero. The phrase "with respect to a basis" means that the rows (and columns) of the matrix are associated with particular element in that basis.
"Do they mean that $M$ has a diagonal representation, as above, and,
that using the specified basis, the matrix representation of $M$ is a
diagonal matrix?"
Yes indeed, provided that $M$ is a normal matrix, it always has a diagonal representation. (This is what the Spectral Theorem states.)
"So, is the matrix representation of $A$ wrt the basis
$\{|0\rangle,...,|n\rangle\}$ simply
diag$\{\lambda_0,...,\lambda_n\}$?"
Well, provided that this basis is the basis in which $A$ is diagonal, then yes, the diagonal matrix contains the eigenvalues on the diagonal.
