I don't believe motor starting flicker is the source of your problem. I have the same issue, and during my time working at a power company, there was actually one client who had this same issue after retrofitting to LED tubes.
The flicker that you notice is well below 60Hz(My assertion, not yours) and is continuous from your descriptions as the compressor runs. The discussion of the starting capacitor or a soft start is actually a totally different problem. What happens when your compressor begins its compression stroke, and proceeds to end it, is that the torque required to turn it increases steadily and then drops off sharply as the compression stroke is finished and the piston passes over top dead center.
This varying motor load results in the line current varying at a lower than 60Hz frequency (typically the compressor turns much slower than 60Hz). As the current varies up and down in phase with the compressor, the voltage drop across your wires also varies, meaning the voltage at the LED bulbs is also going down and then up every time there's a compression stroke.
For reference, my compressor is a behemoth I inherited from my father. It's rated at 5HP and draws 28 amps RMS on a 240V circuit, and still causes this problem. The fact that my pole barn is the furthest thing from the service entrance on the house (and thus the transformer) doesn't help, nor the fact that I have a 10kVA transformer. The compressor operates at about 3-4 Hz (estimated based on my hearing) and the lights flicker about that fast too.
The problem is due to poor light design (assuming your voltage flicker is in spec, and it very well may be, as my former company had done voltage studies on a customer with this problem to see if the flicker was caused due to out-of-spec flicker voltage and found nothing). I haven't torn apart any of the LED tubes I used to retrofit my house, but I suspect they forego active power factor correction circuits in order to make them cheaper, because that type of circuit should be able to compensate for this type of issue(Look up Active PFC).
Whether or not light-strip-in-fixture LED lights have better designed power supplies or not I cannot comment on because they are obnoxiously expensive($80 USD per fixture where I can retrofit a 4ft 4 light LED fixture to LEDs for 10 bucks a bulb at $40 USD!) and that has prevented me from purchasing them.