I am not sure I understand your comment on language structure. E-graphs are used to reason automatically about equivalence of (PL or) math expressions, there is quite a lot of possible combinations of assembly opcodes or other bytecodes and humans interact with them directly but compilers and formal tools have to.
> do not humans interact with them directly but compilers...
So compiler programmers deal with them and humans designed them to be dealt with by the people that write compilers.
There's a major selection bias active here - the e-graph is a reflection of the language (and perhaps the target ISA) and its complexities.
Since at each level it's likely to have been designed for comprehensibility it seems to me unlikely that any given example will be buried in the intractable heart of NP.
But as I said, it's a hunch.
Languages tend to be designed with comprehensibility in mind - so the thoroughly unjustifiable hunch that I'm having is that the vast majority of the extreme complexity possibilities are for languages that no sane human would design, let alone actually work with.