Astoundingly enough, this has already been studied. And I'm almost embarrassed to say that I'm familiar with the result. I used to freecell a lot. And FYI, 11982 is the impossible Frecell game. But I recommend entering in games -1, -2, -3, etc too.
So here are some stats from some studies of freecell. Firstly, the depth of the aces, i.e. how many cards cover the aces, is not a good measure of difficulty. On average, 11.077 cards cover the aces (counting aces). Analyzing the dozens of thousands of deals, it takes an average of somewhere between 42.12 (from a solver that ran 1.5 million deals) and 46.33 (from a solver on 32000 deals, the original 32000) moves to solve. This is a hard measure, as this is based on the quality of the solver - and it is unknown whether these solvers were optimal.
An interesting player-based study showed that about 79% of deals are solved by a person on their first try. It also turns out that some people examine how many freecells (the four in the top left) are actually necessary to solve a game. The impossible 11982 can be solved with 5 freecells. Almost every game can be solved with 3. Over half can be solved with 2. And almost 100 can be solved without any freecells at all. Take that, freecell!
One of the big problems is that freecell games are not at all randomly assorted, and so pencil and paper solutions aren't around. But lots of people have (surprisingly) cared about these questions, and so these results are all upper bounds. In short, about 45 moves is the average minimum.
References:
[1] http://solitairelaboratory.com/fcfaq.html
[2] http://scscompa.com/MainWebPage/freeceln.htm (which was done by hand, astoundingly)