cdlatex is not need it.
The manual says you have to install it:
You need to install ‘cdlatex.el’ and ‘texmathp.el’ (the latter comes also with AUCTeX) from NonGNU ELPA with the Emacs packaging system or alternatively from https://staff.fnwi.uva.nl/c.dominik/Tools/cdlatex/.
The manual I linked you to.
Your stack trace confirms: you don't have cdlatex installed (or not in your path) when you are trying to turn on cdlatex mode with turn-on-org-cdlatex.
If that is the best user experience or not I leave to the interested party to lift in a bugreport/request to org devs, but it is what it is, and is documented in the manual.
I don't know what is the problem with cl-lib been loaded in Emacs core. RAM is cheap nowadays. I am loading the entire cl-lib in my Emacs when I build Emacs, no problems noted (been doing this for a while):
In my loadup.el I do this:
In conjunction with this, I have also patched cl-lib.el to remove some unnecessary loading when bootstrapping:
The reason is I just prefer to have it in loadup.el explicitly so I can see it and comment/uncomment if need be, instead of perhaps forgetting cl-lib.el does it on the bootstrap.
You can make those as patches and apply patches automatically when building Emacs.