The stall-current of the servo is the culprit probably - until the servo's moving there is a spike of current limited only by the resistance of the motor windings. 0.1uF would never be enough for this, such spikes are typically many ms and many amps, so mF are needed.
A 'better' solution would be a separate regulator for the servo power and maybe add a more modest capacitor on the Arduino 5V line. Or is that what your circuit actually is? ("with a high current bypass circuit")