Maybe it's not that relevant to contrail formation since nuclei are always present, yes?
Well, no. There are two kinds of nuclei.
There are Cloud Condensation Nuclei. There are plenty of them and they are everywhere. You cannot get water supersaturated air (in the free atmosphere), that is RHw above 100% because the CCN are always there to initiate condensation.
There are Ice Nuclei. There are very few in the free atmosphere. Aircraft exhaust provide them in the exhaust plume, and they are in the condensed water droplets, and the droplets readily freeze on them.
Ice will not nucleate on a condensation nucleus; it needs an ice nucleus.
That there are none (or very few) naturally occurring in the atmosphere is why you can have vast regions of ice-supersaturated air where the RHi is above 100%, and up to like 140% at the point where RHw is just reaching 100%.
And this is why large parts of the sky can be filled with persistent contails that cannot dissipate in these ice-supersaturated regions.
If there were Ice Nuclei, then these ice-saturated regions would be full of ice cloud, just as water-saturated regions are full of water droplet cloud.