Think about what each input pulse means. It's once cycle of your input waveform. But not only that, it's all the information you have available.
Create a regular clock, a regular sampling pulse in your DSP to run your filter. This must be faster than the highest frequency you sample. If 1kHz is the highest frequency you measure, then 2kHz would be a reasonable sampling rate.
At each sampling interval, you have either had a cycle of input, so the frequency for that interval is 1, that's one cycle per interval, or you have not, so a frequency of zero.
For instance if you had a 500Hz input signal with a 2kHz internal sampling clock, your data would look like 0, 1, 0, 0, 0, 1, 0...
The density of 1s is the frequency, but it's very noisy at the moment and needs to be low pass filtered. Once you have lowpass filtered this sufficiently well, you would get 0.25, 0.25, 0.25, which indictates your input frequency is 0.25 of your sampling rate.
As you will need a relatively long time constant, an IIR filter would seem to be a good bet. You could also try a CIC (Hogenhaur) filter if you wanted to use a recursively implemented FIR.
As you have used all the information in the input signal, this is as good as it gets with a linear filter. All you can do is switch between a very low frequency filter with long delay, or a wider band filter with less delay.
However, you might be able to improve things subjectively a little with a non-linear pre-processing stage before your low pass filter.
You could do a first order hold on the edge data. Instead of shifting 1s and 0s into your filter, you could shift in 1/Ns, where N is the number of sampling pulses that have elapsed since the last input edge. This will introduce a frequency response, but I suspect that it will not matter in your crude application.
For instance, if the frequency was 1kHz and then suddenly changed to 500Hz, the input to your filter would be 0.5, 0.5, 0.25, 0.25, 0.25, 0.25. Notice that two cycles of 0.5 and four cycles of 0.25 both sum to 1 input clock edge. Now the filter is starting with a 'nicer' signal.
This method could produce quite serious errors if the frequency suddenly changes downwards. For instance after two pulses separated by 1mS, so outputting 0.5 into the filter, the next pulse takes 1 second to arrive. For the whole of that second, the frequency estimate is too high. This could be mitigated by a) once you have outputted a complete cycle's worth of frequency data and the next pulse has not arrived, switch to outputting zero or b) once the delay exceeds 1/the_output, switch to outputting 1/delay since last pulse. This is not correct either, but has less latency than not doing it, and is smoother than (a).
It depends what qualities you want in your final filtered output, do you want it to look pretty, or do you want it to be 'correct' in some signal processing sense. You can't magically create information out of nothing, and your pulse arrivals have severely limited the information available to you. You can only do with this data the best you can.