>Turns out... they are not! You can do the same thing using a different set of functions, like Legendre polynomials, or wavelets.

Yup, any set of orthogonal functions! The special thing about sines is that they form an exceptionally easy-to-understand orthogonal basis, with a bunch of other nice properties to boot.