I think it would be easier for me to understand the second part of your answer if we consider a small concrete example, so I asked a separate question about the two universes $\ast$ and $\square$ from CoC.

One question that I didn't include to my new post: if we use Tarski-style universes and if we want to get a consistent logical theory, can the length of the chain $U_i: U_{i+1} : \dots$ be finite? I'm thinking about CoC, which is consistent, and where we have two universes $\ast$ and $\square$ such that $\ast:\square$. As far as I understand, for Russel-style universes, an infinite chain is needed to avoid things like $U:U$.

Sure it can be finite. It is for LF. The top-level universe is simply not a term of any other universe. The universe being Tarki-style or Russell-style doesn't change that. (This is why LF doesn't have a code for $\mathsf{Type}$ and a corresponding $El(\mathsf{type})=\mathsf{Type}$ equation. If we did add those, we'd almost certainly run into inconsistency, because those would effectively be saying $\mathsf{Type}:\mathsf{Type}$ from a Russell-style perspective. So we just don't add those.)

The benefit of an infinite hierarchy of universes (besides power) is that we can uniformly say that every term is classified by some type. This avoids the need for a parallel set of rules for terms that are not classified by some type. You can see this happening in LF where we need a separate $\Gamma\vdash K\ kind$ judgement distinct from $\Gamma\vdash k:K$ judgement with a lot of parallel rules.

Let's consider Calculus of Constructions again. In it, there isn't an infinite hierarchy of universes, there are only two universes if my understanding is correct. So I was wondering if there is any example of a term in Calculus of Constructions that wouldn't be "classified by some type"? And what is the "parallel set of rules" in the case of CoC? I only know of these rules, is there anything else?

If you treat $\square$ as a term (which is probably not the case), then it is a term that is not classified by a type. If you don't treat it as a term (and in the original description there was no $\square$), then $*$ is a term that isn't classified by a type, and $(-)\vdash(-):\square$ should be treated as a binary relation and not a special case of the trinary $(-)\vdash(-):(-)$. The parallel rules in your description are encoded by the $s$ (meta-)variables which can be either $*$ or $\square$. In the original description, these parallel rules are more explicit, e.g. there's $$\dfrac{\Gamma[x:M]\vdash\Delta}{\Gamma\vdash[x:M]\Delta}\quad\text{and}\quad\dfrac{\Gamma[x:M_1]\vdash M_2:*}{\Gamma\vdash[x:M_1]M_2:*}$$ The rules you list leverage presentational innovations from Pure Type Systems which came after and were, in part, inspired by the original description of the Calculus of Constructions.