OK, my bad, Fulton's Algebraic topology: A First Course only deals with the closed case. I'll suppose that you know this case quite well.
Let's do the bounded case by hand.
First case: one boundary component
Keep in mind the classical decomposition of the closed surface $F_{g,0}$ of genus $g$ : you have 1 vertex, $2g$ edges, and that $2$-cell whose boundary gives the complicated $[a_1,b_1]\cdots[a_g,b_g] = 1$ relation.
Now, take a needle, and pierce a hole in the middle of the 2-cell. You get $F_{g,0} \setminus \textrm{a point}$. Deformation retract the pierced 2-cell on its boundary: that creates a movie whose opening scene is this pierced surface, and whose closing scene is the $1$-skeleton, which is a wedge of $2g$ circles (the $a_i$'s and the $b_i$'s). What happens in the middle of the movie? Well, you have a surface with a disc-shaped hole which expands with time. Topologically, it's exactly the surface $F_{g,1}$ of genus $g$ with 1 boundary component.
So we have learned two things:
- Piercing a surface (i.e. taking a point out) or making a true hole in it (i.e. take an open disc out) gives the same result up to homotopy equivalence [that's quite irrelevant for our discussion, but it's good to know nevertheless. Of course it works for many other spaces: they only have to be locally not too complicated].
- A pierced surface has the homotopy type of a graph. This is quite important for the study of surfaces. In particular, it gives the wanted presentation:
$$ \pi_1(F_{g,1}) = \left\langle a_1, \ldots, a_g, b_1, \ldots, b_g\right\rangle.$$
Of course, because the boundary of the surface is associated to the word $[a_1, b_1]\ldots[a_g, b_g]$, you can choose to write this group
$$ \pi_1(F_{g,1}) = \left\langle a_1, \ldots, a_g, b_1, \ldots, b_g,x \middle| x = [a_1,b_1]\cdots [a_g, b_g]\right\rangle$$
but this quite obfuscates the fact that this group is free.
Second case: the sphere with holes
Take now $F_{0,b+1}$, the sphere with $b+1 > 0$ boundary components. You can see it as the disc with $b$ boundary components. This amounts to choosing one of the boundary components and declaring it the "outer" one. It's quite easy to retract that on a wedge of $b$ circles, so that
$$\pi_1(F_{0, b}) = \left\langle z_1, z_2, \ldots, z_{b}\right\rangle.$$ In this presentation, the (carefully oriented) bouter boundary component is simply the product $z_1\cdots z_b$.
The general case $F_{g,b}$
You can write the surface $F_{g,b}$ of genus $g$ as the union of $F_{g,1}$ and $F_{0,b+1}$, gluing the boundary of the former with the outer boundary of the latter. Since we have computed the fundamental groups of the two pieces and that we know the expression of the gluing curve in both of them ($[a_1, b_1]\cdots[a_g,b_g]$ and $z_1\cdots z_b$, respectively), the Van Kampen theorem gives us the answer
$$\pi_1(F_{g,b}) = \frac{\left\langle a_1, \ldots, a_g, b_1, \ldots, b_g\right\rangle * \left\langle z_1, \ldots, z_b \right\rangle}{\langle\langle [a_1, b_1]\cdots[a_g,b_g] \cdot (z_1\cdots z_b)^{-1}\rangle\rangle} = \left\langle a_1, \ldots, a_g, b_1, \ldots, b_g, z_1, \ldots, z_b \middle| [a_1, b_1]\cdots[a_g,b_g] =z_1\cdots z_b \right\rangle.$$
It is probably worth noting that you can rewrite the relation so that it expresses $z_b$ (say) as a word in the other generators. You can then eliminate it and notice that this is also a free group (again, as long as $b > 0$, $F_{g,b}$ deformation retracts to a graph).
Best Answer
In case anyone is interested in my solution, here it is. I talked to a few other people to get some ideas, and used the feedback I got here as well.
Using the idea to take a surjection $\pi_1(S_g)\rightarrow\Sigma_3$, I found an index 3 subgroup of $\pi_1(S_g)$. The map is $$\phi:\langle a_1,b_1,\dots,a_g,b_g\Big|[a_1,b_1]\cdots[a_g,b_g]\rangle\rightarrow \Sigma_3$$ $$a_1,a_2\mapsto (12)$$ $$b_1\mapsto (13)$$ $$b_2\mapsto (23)$$
(all other generators map to $e$, but I'll continue with just the case for $g=2$ for simplicity).
Then $\langle (12)\rangle$ is a non normal index 3 subgroup of $\Sigma_3$, so $$\phi^{-1}(\langle(12)\rangle)=\langle a_1,a_2,b_1^2, b_2^2, b_1b_2b_1^{-1},b_2b_1b_2^{-1}\rangle$$
is a non normal index 3 subgroup of $\pi_1(S_g)$.
So far this isn't really adding anything to the responses I got, but I was really interested in a geometric picture of what was going on. After a bit of fiddling around I ended up with this picture.
Thanks for the input, everyone!