After a while I found an answer in the literature, so I'm posting it here in case it is useful to someone else.
It is in fact possible to re-balance clique-width expressions so that they have logarithmic depth. The result is given in the paper "Graph operations characterizing rank-width and balanced graph expressions" by Courcelle and Kanté, WG '08. I quote ...
Cographs have clique width 2, and the number of cographs of size $n$ is asymptotically equal to $3.56^n$.
I am not sure how many graphs with a given clique-width $k$ exist.
I will try to answer this old question of yours, although I am not sure my answer is conclusive but it should point you in the right direction.
First let us discuss linear clique-width.
If a graph has linear clique-width $k$, and one add $1$ vertex to the graph, that vertex can always be placed first in the ordering with a unique color.
Hence linear clique-...