How different can the constituents of an Ehrhart quasi-polynomial be?

Let $d=\dim(P)$. First, since $L(t,P)$ is non-decreasing in $t$, for any positive integer $n$ we have $$f_i((n-1)D+i) \leq f_j((n-1)D+j) \leq f_i(nD+i) \leq f_j(nD+j)$$ whenever $i \leq j$. Thus it is easy to see that the coefficients of $t^d$ in $f_i,f_j$ must be the same (in fact this coefficient is a normalized volume of $P$). Thus $f_i(t)-f_j(t)$ is $O(t^{d-1})$.

It is easy to see that $\Omega(t^{d-1})$ can be achieved. For example, if $P$ is the $d$-cube with side-length $1/2$ in the positive quadrant with a vertex at the origin, then $$f_1(t)=\left(\frac{1}{2}\right)^d (t+1)^d$$ and $$f_2(t)=\left(\frac{1}{2}\right)^d (t+2)^d$$ so the difference is at least $\frac{d}{2^d}t^{d-1}$. Probably one can improve this constant.

I'll complement Christian's answer with an example in the other direction. Consider the polytope of $8\times 8$ symmetric doubly-stochastic matrices with 0 diagonal. The period of the Ehrhart quasipolymonial is 2 and the degree is 20. However the difference between the polynomials for even and odd dilations has degree only 5. I don't know (but would like to know) what happens for larger matrices.