Being orthogonal, and although fast algorithms exist, Fourier techniques ultimately resorts to least-squares spectral analysis, i.e. finding a sum of terms in the shape of
$$ a_k \cos(\cdot) + b_k \sin(\cdot) $$
which can be solved by linear algebra, with pure real computations. Just remember that, at the time of Fourier (1768-1830), complex arithmetic was not fully developed. Carl F. Gauss (1777-1855) is sometimes credited of the first uses of fast techniques to solve it.
So yes, you can avoid complex numbers, but $ a \cos(\phi) + b \sin(\phi) $, being real with $a$, $b$, $\phi$ reals, is just completely equivalent to some complex number. And complex numbers are just fundamental to the analysis of linear time-invariant systems, because they form their invariant eigenvectors, or allow to diagonalize them.