Hardness of maximizing difference of functions
I suspect there's not likely to be any characterization that is very useful.  The optimization problems can be hard or easy depending on $g$.
To give an analogy: you could ask for a characterization of functions $f$ for which it is NP-hard to maximize $f$.  Well, you're probably not going to find a useful one.