A purse the same color as the lights that flickered overhead.
versus
A purse the same color as the lights flickering overhead.
What's most important is to say what you mean. If you mean that the flickering was ongoing, then "flickering" might be the better choice. However, it should be understood that a continuous action
can be described by a past tense verb ending in "ed." In other words, you don't always need an "ing" verb to describe a continuous action.*
For example: "Lightning bugs flashed all around me as I walked through the forest." No one would assume each bug flashed once and then stopped. So you wouldn't need to say, "Lightning bugs were flashing all around me as I walked through the forest."
So, in your example, if you have previously mentioned that the flickering was continuous, then "flickered" would work. If, on the other hand, this was the first you mentioned the flickering, the reader wouldn't know if it was continuous or a one-time flicker.
Another construct you might consider is changing "flickering" from a verb to an adjective.
A purse the same color as the flickering lights overhead.
or even
A purse the same color as the flickering overhead lights.
I like the second construct, but most people seem to use the 1st. Not only is the 2nd shorter, but to me, it fits the continuous action (they are always flickering) better.
If making the sentence short is important to you, you can omit "same." This would require changing "as" to "of."
A purse the color of the flickering lights overhead.
I know your sentence is just an example, but if it's actually a sentence in your story, then I feel I should point something out. You're describing the color of the purse by comparing it to the color of the lights, but you never mention any color. If you've previously described the lights' color, then you're cool. If not, the description is meaningless.
Which one do you prefer? And how does "that," which has always been a very mysterious word to me, work its magic here?
In your sentence, "that" is a pronoun that ties the phrase (flickering overhead) that follows to the noun (lights) that precedes it to modify the noun.
*Note that some past tense verbs don't need any modification (ed or ing) to denote an ongoing action. For example:
The world
spun as it orbited the sun.