I can also highly recommend 3Blue1Brown's treatment of the topic: https://www.youtube.com/watch?v=spUNpyF58BY (...which I see now is cited in the video that you link to!)

I have a Bachelors and Master's in Electrical Engineering and do some signal and image processing as part of my job. I've been working with FFTs since undergrad and I thought a good understanding of what it does and how it works. But that Veritasium video helped me put all the pieces together in a way that made things click.

The famous 3Blue1Brown video is also very strong and maybe explains why complex numbers are used better.

Of course both videos leave stuff out in the interest of time but they should both be part of a signal processing curriculum.

You might also enjoy this Engineering Guy video playlist on how a mechanical harmonic analyzer works.

https://youtube.com/playlist?list=PL0INsTTU1k2UYO9Mck-i5HNqG...

For an additional video exposition, I also like Eugene Khutoryansky's "Fourier Transform, Fourier Series, and frequency spectrum"

https://www.youtube.com/watch?v=r18Gi8lSkfM

In particular, the visualization of the addition of sine waves of different frequencies in three dimensions is pretty spectacular. It's similar to Mathologer's "Epicycles, complex Fourier series and Homer Simpson's orbit":

https://www.youtube.com/watch?v=qS4H6PEcCCA