The restricted isometry property (formerly known as the uniform uncertainty principle) for random Fourier measurements prohibits $\varepsilon$ from being smaller than about $\log^{-6} N$ in the case that $G = {\bf Z}/N{\bf Z}$ is a cyclic group; see Lemma 4.3 and Definition 1.2 of [this paper of Candes and myself][1].  Indeed, if one takes $S$ to be a random subset of $G$ of density $1/2$, then for any sufficiently sparse $f$ (less than $c N/\log^6 N$ for some small $c$), the Fourier energy of $\hat f$ will be split more or less equally between $S$ and its complement thanks to the RIP.  It is likely that the methods of proof also work for other abelian groups than the cyclic groups, but we did not pursue this explicitly in that paper.

The oversampling factor of $\log^6 N$ is probably not best possible; the [work of Rudelson and Vershynin][2], in particular, suggests an improvement to $\log^4 N$ is possible.  If one takes gaussian measurements instead of Fourier ones, one only needs to oversample by a constant factor (see Lemma 4.1 of the previously mentioned paper of Candes and myself and the remark at the end of the proof), so it is conceivable that one can give a negative answer to your question for some sufficiently small $\varepsilon$ independent of the size of the group.  But unfortunately this is probably outside of reach of the technology described in the above papers.  (But there has been a number of advances in that area since then, which I have not followed as closely.)


  [1]: http://arxiv.org/abs/math.CA/0410542
  [2]: http://arxiv.org/abs/math/0602559