Why does Fourier analysis of Boolean functions "work"? Over the years I have gotten used to seeing many TCS theorems proved using discrete Fourier analysis. The Walsh-Fourier (Hadamard) transform is useful in virtually every subfield of TCS, including property testing, pseudorandomness, communication complexity, and quantum computing.

While I got comfortable using Fourier analysis of Boolean functions as a very useful tool when I'm tackling a problem, and even though I have a pretty good hunch for which cases using Fourier analysis would probably yield some nice results; I have to admit that I'm not really sure what it is that makes this change of basis so useful.

Does anyone has an intuition as to why Fourier analysis is so fruitful in the study of TCS? Why so many seemingly hard problems get solved by writing the Fourier expansion and performing some manipulations?

Note: my main intuition thus far, meagre as it may be, is that we have a pretty good understanding of how polynomials behave, and that the Fourier transform is a natural way of looking at a function as a multilinear polynomial. But why specifically this base? what is so unique in the base of parities?
Here is my point of view, which I learned from Guy Kindler, though someone more experienced can probably give a better answer: Consider the linear space of functions $f: \{0,1\}^n\to\mathbb{R}$, and consider a linear operator of the form $\sigma_w$ (for $w\in\{0,1\}^n$), that maps a function $f(x)$ as above to the function $f(x+w)$. In many of the questions of TCS, there is an underlying need to analyze the effects that such operators have on certain functions.

Now, the point is that the Fourier basis is the basis that diagonalizes all those operators at the same time, which makes the analysis of those operators much simpler. More generally, the Fourier basis diagonalizes the convolution operator, which also underlies many of those questions. Thus, Fourier analysis is likely to be effective whenever one needs to analyze those operators.

By the way, Fourier analysis is just a special case of the representation theory of finite groups. This theory considers the more general space of functions $f:G\to \mathbb{C}$ where $G$ is a finite group, and operators of the form $\sigma_h$ (for $h\in G$) that map $f(x)$ to $f(x\cdot h)$, The theory then allows you to find a basis that makes the analysis of such operators easier - even though for general groups you don't get to actually diagonalize the operators.