Egan's stories are often of the "one big lie" variety. He makes up some fact (e.g. fundamental particles are composed of 12-dimensional wormholes, we live in an uncountably infinite multiverse that can be traversed, you can build a machine that combines a space and time dimension, etc.) and then follows the made-up fact to some fascinating conclusion. He is clearly very intelligent and has substantial background in many scientific fields, which makes his sci-fi books quite mind-bending.
One of the nice things about mathematics is that we don't need to say anything like that.
Probabilities are nature's probability techniques. Functions are nature's function techniques. And compression is nature's set of compression techniques.
You might find category theory useful here.
Take the category Set, which is the category of sets. Just imagine an n-dimensional structure of dots and arrows, where the dots and arrows can each represent some other n-dimensional structure of dots and arrows. Set is the structure of that form which is constrained precisely so that it represents the idea of sets, and functions between them.
You can consider other structures like Set that are constrained (or freed) to represent all manner of properties, structures and other stuff. Some of this stuff resembles branches of mathematics. Some resembles physics. Some resembles philosophy.
Science takes observation and uses mathematical models to transform that observation into prediction. So long as a model is sufficiently general, in a computational sense, then you will find that you _can_ rewrite the whole of science in terms of that model. But this doesn't consider the question of elegance -- and the related question of what you want to consider fundamental. And the product question of those two: how do you measure/compute most effectively to maximize elegance-of-stuff upon that fundamental-structure?
As someone who cares deeply about constructive mathematics, I consider things like topoi, the Curry-Howard(-Lambek) isomorphism, and Grothendieck's relative perspective to be fundamental, and a beautiful foundation for the modelling of any and all information dynamics (≃ 'nature', 'thought', 'computing'). You may have some other perspective. There is a vast space of ways to approach the problem of modelling experience.
To be scientific, the thing to avoid is appending some _intention_ to the processes that your model describes. Causality is real and everywhere, but there is no way to say "nature compresses by using probability and functions" that doesn't beg the question. Either compression, probability and functions are part of your singular model of nature, or they are competing models. You do math -- or coming from different directions you do physics, info theory, etc. -- by finding a general method that reworks them as a coherent idea.
You're doing the first step of that when you form a surface analogy between (probability,functions) ≃ (nature,compression).
If this kind of question bothers you enough, you can make it your life's work to follow the rabbit hole all the way down. It's not so much a question of smartness (though rigor is a huge part of truth-seeking) -- just how inexorably bothered you are by the idea of competing models of reality.
Cryptography, machine learning, and complexity theory are immediate implications of analogies similar to your own (p,f)≃(n,c). Should you want to study further (and don't particularly identify with the constructivist tone of this comment), those are probably the most appropriate fields in which to look for elegant solutions to your questions.
I see things like quantum mechanics and think about how instead of say at the deepest levels of nature that instead of somehow enumerating all the possible positions of an electron or particle it was more efficient to somehow make it probabilistic. Likewise for things like fractals instead of having a ridiculously high-degree polynomial function you have a simple polar function or the examples in the article that make elegant designs from a simple formula.
I am rambling at this point but I appreciate your links. I already went down the rabbit hole on the Wikipedia ones.
As an aside when I took a MSCS class in cryptography I had to refresh on set theory and remember enjoying that and I guess is what got me thinking about these types of things again.
Minimum description length might be just the right place.
Alternately, generating functions.
Alternately alternately, various categorical notions.
Alternately alternately alternately, foundational madness of the best kind.