Hi Jon, I think it's a bit different in terms of scaling from some of the things you said (if I'm understanding correctly).
What you said about diagonalizing the left/right cut density matrix is correct, assuming the wavefunction is already in the form of an MPS with bond dimension m. Then one can trace all of the sites in the right half, say, and use the MPS tensors to express the reduced density matrix for the left half completely in terms of the virtual indices connecting left to right, so indeed an m x m matrix which would have a cost of m^3 to diagonalize.
But based on how I would think about the other case, that of some 3 site block in the center, is that its reduced density matrix would be a d^3 x d^3 matrix, where d is the local site dimension, since one would trace all sites except the central 3. Then it would scale as (d^3)^3 or d^9 to diagonalize.
Oh but now I see what you're thinking maybe, which is to get the density matrix for the *complement* of the 3-site region by just tracing over those three sites. In that case, yes, the density matrix computing that way from an MPS would have dimensions m^2 x m^2 so would cost (m^2)^3 = m^6 to diagonalize.
So for three sites in the middle, it's much more likely that the cheapest way to do things is to do the first option of tracing all but the three sites, rather than the other way around. But for more sites eventually switching to doing things the other way would be cheaper. Either way it would be an expensive operation.