For me, the "a-ha" moment with Fourier transforms was when I related it to resolving a vector into components. If you have a vector in some arbitrary direction and for convenience of calculation or representation you want to express it as the sum of scalar multiples of another pair of vectors (let's call them the "basis pair"), you use the dot product of that vector with each of the basis vectors (divided by the basis vector's magnitude) to find something that could be called "the shadow of that vector projected along the line of the basis vector".
In a simple case, the basis pair could be the horizontal unit vector and the vertical unit vector--that's what you're most familiar with--but any two vectors that don't lie along the same line can be used, you just have to project the vector you're looking at along the line of each vector in turn and see what a and b you need to use as a multiple to get a times {one vector} plus b times {the other vector} to add up to your original vector. Fourier transforms use a similar idea--"I've got this complicated wave form, let me see if I can break it up into a sum of multiples of simpler wave forms."
Think about the Fourier transform on a sound wave as an example. What you're basically doing is projecting the sound wave onto a pure 440Hz signal and saying "it's about this much middle A" and then projecting the wave onto a 466Hz signal says "and now about this much B flat". Continuing in this way you would have the tones on a piano as your "basis vectors" and you could reproduce the sound (approximately) by playing each key harder or softer according to what the calculation gave you at each frequency.
To me, this takes some of the "well how would anyone ever come up with this?" mystery out of it. The idea of representing something as a times this basis vector plus b times that basis vector is just being generalized to "I can represent this sound wave as a times this pure sine wave plus b times this pure sine wave, plus c times this pure sine wave" and so on.
I don't know if this is historically where the realization came from, but I think it answers your question in the sense of "how would I ever come up with this idea myself?". You come up with it by thinking of a curve as being the sum of components of an infinite-dimensional vector space. Don't let the "infinite dimensions" mess with your head--in practice, you just get it as close as you need it to be, like with digital music you take the natural sound and sample it over enough different frequencies (basis vectors) that it sounds ok when you play it back as x times this frequency plus y times that frequency plus z times that frequency, etc.
(This is how a Fourier transform on an input wave could be used to digitize music--you go from a natural wave to "play frequency x [a number, stored digitally] at volume y [a number, stored digitally] and, simultaneously, frequency z [a number, stored digitally] at volume v [a number, stored digitally]". You're just "resolving" the music into numerical volume multipliers of numerical frequencies.)
You don't get an exact fit for every possible curve but by using more and more "basis vectors" you get closer and closer to the exact curve.
The "piano keys as basis vectors" idea is not new to me--one of my physics professors showed us how you could yell into an open piano and the sympathetic vibration of the strings would make an approximate Fourier transform of your voice. See also this experiment along those lines in a YouTube video (narration in German but the piano "talks" in English): https://www.youtube.com/watch?v=muCPjK4nGY4
Other concepts in math have a similar basis (pardon the pun). Taylor series expansion and Bernoulli polynomials are similar things where you get close to some function or curve by approximating it with a bunch of scalar multipliers to something that approximates an infinite-dimensional vector space. The process of figuring out what the scalar multipliers are for a given curve usually looks something like the Fourier transform.
