Progressive discrete multifunction optimization
There are two techniques that I suspect might be worth trying in this context:


Simulated annealing. Simulated annealing is a heuristic for optimization that works well when the objective function varies smoothly as a function of its parameters, based loosely upon some structure in the parameter space.  You can find a good discussion of how to use simulated annealing, in Steven Skiena's The Algorithm Design Manual.

In your context, you'll need some operations that tweak $S$ by a little bit.  Basically, you start from a specific choice of $S$ and then make small modifications, seeing which modifications increase the value of $\Phi(S)$, where $\Phi$ is the objective function.  When you find a $S'$ that increases the objective function, you keep that one and start modifying it.  This is basically hillclimbing.  Simulated annealing improves on that by doing random jumps to get out of local optima.

In your context, the objective function is

$$\Phi(S) = \sum_{f \in F} f(S).$$

There are many candidates for how to tweak $S$.  You could try adding a random element of $G$ to $S$ (or adding $k$ randomly chosen elements of $G$ to $S$) as one operation; removing a random element (or removing $k$ elements) as another operation; and so on.  Typically you take advantage of your domain knowledge to select a set of operations that might potentially make sense as "sensible" ways to vary $S$ by a little bit.  Then, you let the simulated annealing algorithm take over from there.

The useful thing about your context is that when you've found an optimal value of $S$ for functions $f_1,\dots,f_n$ (i.e., for objective function $\Psi(S) = f_1(S) + \dots + f_n(S)$), and then you later get an additional function $f_{n+1}$ to add to the set, now $S$ is a reasonable starting point to start the optimization process for $f_1,\dots,f_{n+1}$ (i.e., for objective function $\Psi'(S) = f_1(S) + \dots + f_{n+1}(S)$).  In particular, given your structure, we might expect that the optimum for $\Psi'$ might be "close" or "similar" to an optimum for $\Psi$, so the optimum for $\Psi$ is a good place to start the hill-climbing/simulated annealing for $\Psi'$.

To extend on that idea, you might also try remembering multiple values of $S$ from the previous round: say, sets $S_1,\dots,S_m$ that give the $m$ largest values of $\Phi(\cdot)$ that you encountered during your optimization with the objective function $\Psi$.  Now, when you add another function in the next round
and want to find an optimum for $\Psi'$, you could try starting from each of $S_1,\dots,S_m$ as candidate starting values for the hill-climbing / simulated annealing.  This might be effective in practice -- you'd have to try it out to see.
Memoization. Since computing $f(S)$ is very expensive, you might use memoization to ensure you never compute it more than once.  In particular, you might keep a hashtable with mappings $(f,S) \mapsto f(S)$, so that you never need to compute $f(S)$ for any particular combination of a function $f$ and a set $S$ more than once.  This might help you out.

Also, when starting the optimization process for the objective function $\Psi'$, you might try computing $\Psi'(S)$ for each $S$ such that you computed $\Psi(S)$ in the previous round. Since $\Psi'(S) = \Psi(S) + f_{n+1}(S)$, the memoization will ensure that (if you computed $\Psi(S)$ previously) $\Psi'(S)$ can be computed relatively efficiently: it only requires evaluating $f_{n+1}(S)$, since $f_1(S),\dots,f_n(S)$ will already be in the memoization table.


Finally, if you know anything more about the structure of the $f$'s, you might try looking into branch-and-bound style techniques.

Again, these are just ideas.  You are in the space of heuristics, so there are no guarantees.  You'll have to try out these techniques in your particular application domain to see how well they work.  In practice often you may need to try out different parameter settings and make some application-specific tweaks to these general techniques, so be prepared to experiment and try out different stuff.