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}.$$
For algebraic topology, it really depends on what areas of you'll be studying. If you'll be looking into homology and cohomology, you should read Allen Hatcher's Algebraic Topology (chapters 2 and 3). If you're going to be spending your time on homotopy theory, then I'd recommend Arkowitz' book on Homotopy theory. Hatcher also treats homotopy theory, but I don't particularly like how he goes about that. Arkowitz is better for this, in my opinion.
For algebraic geometry, I don't know that there's a standard 'compact' text which will be of that much use in a first course. Perhaps Miles Reid's Undergraduate Algebraic Geometry.
For both things, I'd recommend learning some category theory. Learn about functors. In both algebraic geometry and algebraic topology we use functors to go from the "geometric" (or topological) world of spaces to the algebraic world of rings and groups (among other things). When you start your algebraic topology course you should aim to understand (for example) how the fundamental group is actually a functor from Top to Grp. When you start doing algebraic geometry, try to understand the functors which you're using there too. It helps understand the bigger picture.
In both cases, an in depth understanding of the algebraic objects at hand is absolutely necessary. In the case of a first course in algebraic topology, group theory is important. In the case of algebraic geometry, ring theory. Particularly a good understanding of polynomial rings is important - but then again, algebraic geometry is basically designed to help us understand those :)
Best Answer
One way to explain the connection is via the Hodge decomposition of the (singular) cohomology groups of an algebraic variety.
On one hand, viewing $X$ as a two-dimensional real manifold, and using say Mayer--Vietoris, one proves that $H_1(X,\mathbf{Z}) \cong \mathbf{Z}^{2g}$, and hence by duality, $H^1(X,\mathbf{C}) \cong \mathbf{C}^{2g}$.
On the other hand, let's upgrade Riemann's theorem to the Riemann--Roch theorem, which says that if $K$ is the canonical bundle (i.e. the bundle of holomorphic 1-forms) on $X$, then $$l(D)-l(K-D) = \mathrm{ deg}\, D + 1 -\gamma.$$ (I changed $g$ to $\gamma$ because a priori this isn't the same as the previous $g$; indeed, that's what we want to prove.) Applying this with $D=0$ we get $$1-l(K) = 1-\gamma$$ hence $l(K)=\gamma$. Now $l(K)$ by definition means the dimension of the space of global sections of the bundle $K$ of holomorphic 1-forms on $X$. Another notation for the same space is $H^0(X,\Omega^1)$, so we have $\mathrm{dim} \, H^0(X,\Omega^1)=\gamma$.
The statement of Hodge decomposition for curves is the following:
\begin{align} H^1(X,\mathbf{C}) = H^0(X,\Omega^1) \oplus H^1(X,\mathcal{O}_X) \end{align}
and moreover the two direct summands on the right-hand side are conjugate, hence have the same dimension $\gamma$. (Don't worry about what $H^1(\mathcal{O}_X)$ actually is if you don't know the definition of sheaf cohomology; all that matters is that it has dimension $\gamma$.)
Now we know the dimensions of both sides of the displayed formula from 1. and 2. above, and plugging them in we get $$2g=\gamma+\gamma;$$ that is, $g=\gamma$!
Edit: Maybe it's worthwhile mentioning a simpler proof for plane curves of the equality of these two numbers.
First of all, it's easy to deduce from the Riemann–Roch theorem that the degree of the canonical line bundle $K$ is
$$\text{deg} \, K = 2\gamma - 2.$$
On the other hand, if $X$ is a smooth curve of degree $d$ in $\mathbf{P}^2$, one can write down an explicit nonzero regular differential $\omega$ on $X$, and observe that it has $d(d-3)$ zeroes. Since $\omega$ is a section of $K$, this shows that
$$\text{deg} \, K = d(d-3).$$ Comparing these two expressions for the degree, we find that $\gamma=\frac12 (d-1)(d-2)$.
So our goal is now to show that the topological genus $g(X)$ is also equal to $\frac12 (d-1)(d-2)$. To do this, we use the fact that $X$ is a degree-$d$ branched cover of $\mathbf P^1$ with $d(d-1)$ ramification points (to see this, project from a general point in $\mathbf P^2$). This gives the formula $$\chi(X) = 2d -d(d-1);$$ since $\chi(X)=2-2g$, this simplifies to give $g=\frac12 (d-1)(d-2)$, as required.