Here by fully factored I mean the expression $x^n - 1$ is fully factored with only integer coefficients.
Ex. $x^6 - 1 = (x-1)(x+1)(x^2-x+1)(x^2+x+1)$. In this case the largest degree of the factors is 2.
Similarly $x^{10} - 1 = (x - 1) (x^4 + x^3 + x^2 + x + 1) (x + 1) (x^4 - x^3 + x^2 - x + 1)$, which has 4 as the largest degree of its factors.
A quick observation would show that for $n=p$ where p is an odd prime, the largest degree would be $p-1$ and for $n = 2p$ where p is an odd prime, the largest factor would be $p-1$
Is there a general formula to find the largest degree?
I think I got it, As jacob mentioned Cyclotomic polynomials was indeed the way to go.
If f(n) is the greatest power of the factors then a generalized formula would be $$f(n) = n - \sum_{d|n}f(d)$$
For example f(20) = 20 - f(10)-f(5)-f(4)-f(2)-f(1) = 20 - 4 - 4 - 2 - 1 - 1 = 8 which is indeed the case (I got the values from the wiki page of cyclotomic polynomials).
The page also had this: $\Phi _{n}(x)={\frac {x^{n}-1}{\prod _{\stackrel {d|n}{{}_{d<n}}}\Phi _{d}(x)}}$ If you consider just the largest exponent of each cyclotomic polynomial we can reach the same formula for f(n)