What is the minimum number of vertices needed to represent a solid of genus $n$ in $\Bbb R^3$?

A general solution is still unknown, but I have a counterexample to the claim $f(1)=9$, in the form of a polyhedron with $7$ vertices and still equivalent to a torus. If the vertices are $v_1,\dots,v_7$, then the face assignment is $(v_1,v_2,v_4),(v_4,v_3,v_1)$ and cyclic rotations of this adding $n=0,\dots,6$ to each index in the set, for a total of $14$ faces. (Note that as in the OP these faces are "oriented sets" determined up to cyclic permutation of the three vertices.) The edges form a complete graph $K_7$, for a total of $21$ edges, and it is easily verified that each edge touches two faces, once in each direction, so it is locally homeomorphic to $\Bbb R^2$ and orientable. Then since $V-E+F=7-21+14=0=2-2g$, we get $g=1$, so it is also toroidal. Thus $f(1)\le 7$. Pictures are a little harder to make, since it seems to be self-intersecting under most attempts at vertex arrangement, but below is a topologically equivalent mapping onto an actual torus.

Edit: An exhaustive computer search has shown that the stated conditions are impossible to satisfy for $|V|<7$ (although there is one polyhedron on $6$ vertices with $\chi=1$), so $f(1)=7$.

By taking connected sums, we can easily iterate this construction to get an upper bound on $f(n)$. Given a $k$-vertex representation of a genus $n$ surface, remove one face from the surface and one face from the above $7$-vertex torus, then glue the holes together. The resulting surface has genus $n+1$ and $k+4$ vertices (because three vertices are overlapped with existing vertices), so we get the bound $f(n+1)\le f(n)+4$ and in particular $f(n)\le3+4n$. One remark: the case $f(0)=3$ corresponds to a triangle with two faces, one oriented up and the other down; this is not excluded as a valid surface of genus $0$ by the combinatorial interpretation, and I leave it to the reader to decide if this is a valid solution to the original question.

But we're not done yet - there's one more optimization we can do. Assuming we are just cobbling tori of this form together, the process above will construct a long line of tori. But we can fold the object onto itself, say by taking one end and gluing it to the other end, which eliminates three vertices and raises the genus by one as well. The prerequisite for not unduly affecting the $V-E+F$ equation is that the two targeted faces must not share a vertex, and indeed must be separated by at least two vertices (i.e. any path from a vertex of one face to a vertex of the other face "the long way round" must contain at least four vertices) so that no edges get folded on top of each other.

The simplest case of this is to fold the two ends together to make a ring of tori instead of a line - this is first possible for the three hole torus construction. At this point we have a ring of $n\ge3$ tori forming a genus $n+1$ surface and using $4n$ vertices (which proves $f(n)\le4n-3$ when $n\ge4$). But it gets better. Suppose that $v_{1,2,4}$ of torus $t_n$ is connected to $v_{6,3,5}$ of each $t_{n+1}$ in the ring, so that $v_7$ is unique to each torus and $v_{1,2,4}$ are shared between two tori. We will use the face $v_{4,6,7}$ of each torus as a connection point - note that this face is one edge away from the equivalent face on the next torus.

So now consider $n$ rings of $n-1$ tori each, and connect every ring to every other ring in a giant $K_n$ mimic. The rings act as big vertices, with $n-1$ connection points to the other vertices. Note that in the worst case we have three adjacent connection points in a triangle, which since the connection points are separated by one edge the triangle cycle separates the connection point from itself around the cycle by three edges, which as mentioned above is sufficient to maintain all edges so that the genus is not affected any more than it should be. Now for the accounting: each ring is $4(n-1)$ vertices, for a total of $4n(n-1)$, and there are $n(n-1)/2$ connections, each saving $3$ vertices each, so we count $5/2n(n-1)$ total vertices. For the genus, since $g-1=-\chi/2$ is additive over disconnected pieces, the genus of the rings is $n(n-1)+1$, and each connection raises the genus by $1$, so the full structure has genus $3/2\,n(n-1)+1$. Thus $f(3/2\,n(n-1)+1)\le5/2\,n(n-1)$, or $$f(n)\le\frac53n\quad\mbox{for infinitely many }n;\qquad f(n)\le\left(\frac53+\epsilon\right)n\quad\mbox{for sufficiently large }n.$$

I highly suspect that $f(n)\ge n$ or at least $f(n)=\Theta(n)$, but a proof is of course not forthcoming. One thing that can be done in the way of lower bounds comes from the observation that since each edge touches two faces and each face touches three edges, $3F=2E$, so $2-2g=V-E/3$, and if $|V|=f(n)$, then since $E\le{f(n)\choose 2}$, we get

$$2-2n\ge f(n)-\frac{f(n)(f(n)-1)}6\implies f(n)\ge\frac72+\frac{\sqrt{48n+1}}2\ge2\sqrt{3n}.$$