Can somebody please tell me why do we have those tiny random spikes on the output signal? And why does the input wave behave like in the picture when we reduce the frequency of the noise source to 1kHz?
The "tiny random spikes on the output signal" in the red oscilloscope trace are noise from the circuit (at test point "IN") that provides the input to the FET gates in your CMOS inverter. IN is equal to Vin (principal square wave) plus Vnoise (100 kHz sine wave). The square wave varies from 0V to 5V. The 1.5V peak noise is added to this, producing a square wave that varies from 0V +/- 1.5V to 5V +/- 1.5V. The Gate-Source voltage (VGS) determines whether either the p-channel or n-channel FET will turn "on," either pulling the signal "OUT" up or down. The noise level is not sufficiently close to the threshold Gate-Source voltages to interfere, so a clean, inverted (NOT) output (blue trace) is produced. As mentioned by Atomique, the +/- 1.5V is close to typical or maximum VGS thresholds, so there might be a little conduction in reality.
In the case of the low frequency (1 kHz) noise source, your square wave is riding on a low frequency sine wave that, from the oscilloscope trace, appears to have about a 2V range. In this case, when a minimum of the square wave (0V) concides with the maximum of the sine wave (2V), you have a missing square wave where the n-channel FET (Q3) does not turn off because VGS stays above its maximum threshold value spec.