Proving skip-lists strongly weight-balanced in expectation
As you asked it, the question about the expected length (given the height) does not make sense without a prior distribution on the length of the string.

You should instead consider the number of times you get tails before you get $h$ heads in a row, since this will give you the number of descendants of a node of height $h$ in a skip list.  Let's represent this value with the random variable $X=X(h)$.  When we start, or right after we get tails, the probability of starting and finishing a run of $h$ or more heads before getting tails again is $2^{-h}$.  If we hit tails before getting $h$ heads in a row, we're back to square one.  Thus $X$ is actually distributed as $\mathrm{Geometric}(2^{-h})$ and we have $\mathrm{E}(X) = (1-2^{-h})2^h$.

Edit: 

Sorry, this gives you the expected number of towers in the left subtree.  The number of nodes in the left subtree will be of the same order of magnitude though, since towers in between the first and last will have geometrically distributed height with expected value 2.  Also, if you want to consider the right subtree as well, which probably makes more sense, you simply go until you get $h+1$ heads in a row instead of just $h$.  In this case you get the number of descendants as defined in Devroye's paper that you linked to.