We don't have precise metrics for "always or almost always loaded at startup", I think.

But cl-lib is unconditionally required by 191 files under lisp/, right now. Including things like
desktop, help-fns, help-mode, kmacro, imenu, tab-line and package, among many others.
And of course vc, Calc and Org. And use-package, which will perhaps become the de facto
way to customize their .emacs for many people.