This is not a complete answer, just some related thoughts. I don't really know about the size that you define; the following (and the Mayr-Meyer paper) are about the degree of the $g_i$. In 1926 Grete Hermann showed an upper bound that is doubly-exponential in the number of variables $k$. The Mayr-Meyer example, a binomial ideal, shows that her bound is sharp.
The Castelnuovo-Mumford regularity of an ideal is probably the most important invariant in this context. In "What can be computed in algebraic geometry" Bayer and Mumford explain that bounding the regularity in terms of the degrees of the generators allows to measure how complicated an ideal is. The regularity is nice because it is connected to free resolutions (degrees of relations) and vanishing of local cohomology (making it computable in some cases). There are examples where the regularity is doubly-exponential in the generating degree, but in many 'geometrically nice' situations one gets better bounds.
For one example: In "Gröbner bases of toric varieites" Sturmfels shows that there is an exponential bound for the regularity of toric ideals (which are essentially binomial prime ideals).
In general it is a different and more complicated story to bound the regularity in terms of the degrees in a Gröbner basis as those are usually higher than in a generating set.
Another interesting result is due to Kollar ("Sharp effective Nullstellensatz") which shows that writing 1 as a member of an ideal with empty variety can be done with coefficients of exponentially bounded degree.