  Despite their appealing features, models with gauge-mediated supersymmetry
breaking (GMSB) typically present a high degree of fine-tuning, due to the
initial absence of the top trilinear scalar couplings, $A_t=0$. In this paper,
we carefully evaluate such a tuning, showing that is worse than per mil in the
minimal model. Then, we examine some existing proposals to generate $A_t\neq 0$
term in this context. We find that, although the stops can be made lighter,
usually the tuning does not improve (it may be even worse), with some
exceptions, which involve the generation of $A_t$ at one loop or tree level. We
examine both possibilities and propose a conceptually simplified version of the
latter; which is arguably the optimum GMSB setup (with minimal matter content),
concerning the fine-tuning issue. The resulting fine-tuning is better than one
per mil, still severe but similar to other minimal supersymmetric standard
model constructions. We also explore the so-called "little $A_t^2/m^2$
problem", i.e. the fact that a large $A_t$-term is normally accompanied by a
similar or larger sfermion mass, which typically implies an increase in the
fine-tuning. Finally, we find the version of GMSB for which this ratio is
optimized, which, nevertheless, does not minimize the fine-tuning.
