If I have $n, 1 < i < n, $ surfaces composed of $f_i$ faces and $v_i$ vertices, how would I go about finding the average surface?
(I'm unsure what I mean by average - intuitively it's obvious, but mathematically I am not sure how to express it...)
I too am unsure what you mean by "average", but any sensible response to your question should surely involve the recent work of Babson, Hoffman, and Kahle on random 2-complexes (there's a sharp threshold for simple connectedness! It's cool!) and the works cited therein by Linial-Meshulam and Meshulam-Wallach.
Your question is quite underspecified, and so difficult to answer. Let me narrow it considerably, perhaps well beneath your interests, to convex polyhedra. Then you can use this result: The convex combination of convex sets is itself convex.
Here is an (entirely skippable) proof. Let $A$ and $B$ be two convex sets, and $C= \alpha A + \beta B$ a convex combination, with $\alpha,\beta \ge 0$, $\alpha+\beta=1$. Take two points in $C$: $$ c_i = \alpha a_i + \beta b_i $$ $i=1,2$. Now consider any convex combination of $c_1$ and $c_2$ (with the usual restrictions of the coefficients $\gamma$ & $\delta$): $$ \gamma c_1 + \delta c_2 = \gamma \alpha a_1 + \gamma \beta b_1 + \delta \alpha a_2 + \beta \delta $$ $$= \alpha ( \gamma a_1 + \delta a_2) + \beta ( \gamma b_1 + \delta b_2 ) $$ $$= \alpha a_3 + \beta b_3$$ So this is in $C$; so $C$ is convex.
So, let your $n$ convex polyhedra be $P_1,\ldots,P_n$. Then define their average as $(P_1 + \cdots + P_n) / n$. This will be a convex polyhedron.
But probably you are interested in nonconvex polyhedra? You might be able to proceed by partitioning your nonconvex polyhedron into convex polyhedra, an interesting challenge in its own right (see the 2D equivalent discussed on MO here: "Partitioning a polygon into convex parts").
And as Douglas' question indicated, you might be clearer on whether all your polyhedra have the same genus.