The fourier transform was a really cool example of this. What's another example of these kinds bases, and how would we find find them?
If I understand correctly, the Legendre polynomials are another basis, at least for a certain set of functions. It's kind of cool that you can use the Gram-Schmidt process (used for finding bases for vector spaces) with very few modifications to find that.
A very natural generalization of basic Fourier modes (sines and cosines) are eigenfunctions of the Laplace-Beltrami operator - a fun place this shows up is in spectral geometry processing. If you want to understand this viewpoint in greater generality, the place to start is the spectral theorem.
Is there a nice description of some basis for the vector space of all real-valued functions? I've always seen this question dodged, but it would be cool to read about such a basis.
Perhaps you should start with the question, "what does it mean to have a basis for R^1?", i.e., just the real numbers. One starting point is the Hamel Basis (though perhaps there is a better source than the Mathworld page...)
Here's a good definition (that is slightly more abstract than R^1) of a Hamel Basis. Actually the whole PDF has pretty interesting content.