Here is a graph $\mathcal{G}(S,x)$ associated to a surface and homology class (similar to the 1-skeleton of the curve complex): For a fixed class in $x\in H_1(S;\mathbb{Z}_2)$, consider isotopy classes of embedded multicurves representing the homology class $x$ (one may assume no components are parallel and there are no trivial components). Make this collection the vertices of the graph $\mathcal{G}(S,x)$. Connect two vertices $A, B$ to be adjacent in the graph $\mathcal{G}(S,x)$ if $A\cup B$ are disjointly embedded, and after removing all parallel curves of $A\cup B$, the remaining components bound a pair of pants or a twice-punctured projective plane (this second can only happen if $S$ is non-orientable). I'm not sure if such a complex has been defined before, but there is a somewhat analogous complex defined in the integral homology case by Bestvina, Bux, and Margalit. Also, this is related to a technique of Hatcher-Thurston to undertand surfaces in two-bridge knot complements.
I claim that the maximal Euler characteristic of a surface bounding $\gamma_0\times 0 \cup \gamma_1\times 1$ is the negative of the distance between $\gamma_0$ and $\gamma_1$ in $\mathcal{G}(S,x)$. Put the product metric on $S\times [0,1]$, and make $\Sigma$ into a minimal surface with respect to this metric (Theorem 6.12 of Hass-Scott). Then $S\times t, t\in [0,1]$ gives a foliation by totally geodesic surfaces, and by the maximum principle, they can be tangent to $\Sigma$ in only saddle tangencies (see an argument of Hass, we will assume things are perturbed to be generaic). Thus, for all but finitely many $t$, $S\times t$ meets $\Sigma$ in a finite collection of curves, giving rise to a vertex of $\mathcal{G}(S,x)$. As one passes through a tangency point $S\times t_0$ (assuming things are generic), the intersection changes by a saddle move, giving a surface in $S$ of Euler characteristic $-1$ bounding the curves before and after the tangency. There can never be a closed trivial curve occurring, because this would give rise to a center tangency. Thus, each saddle tangency gives an edge between the adjacent vertices of $\mathcal{G}(S,x)$, and therefore $\Sigma$ gives a path between $\gamma_0$ and $\gamma_1$ in $\mathcal{G}(S,x)$. Conversely, any such path gives rise to a surface.
Of course, there will be many geodesics connecting $\gamma_0$ and $\gamma_1$ in $\mathcal{G}(S,x)$, given by any Morse function on $(\Sigma, \gamma_0,\gamma_1)$ with only index 1 critical points, and I don't expect the distance function to be easy to compute (probably one should use normal surface theory to compute it).