The dynamical cluster approximation (DCA) and its DCA$^+$ extension use coarse-graining of the momentum space to reduce the complexity of quantum many-body problems, thereby mapping the bulk lattice to a cluster embedded in a dynamical mean-field host. Here, we introduce a new form of an interlaced coarse-graining and compare it with the traditional coarse-graining. While it gives a more localized self-energy for a given cluster size, we show that it leads to more controlled results with weaker cluster shape and smoother cluster size dependence, which converge to the results obtained from the standard coarse-graining with increasing cluster size. Most importantly, the new coarse-graining reduces the severity of the fermionic sign problem of the underlying quantum Monte Carlo cluster solver and thus allows for calculations on larger clusters. This enables the treatment of longer-ranged correlations than those accessible with the standard coarse-graining and thus can allow for the evaluation of the exact infinite cluster size result via finite size scaling. As a demonstration, we study the hole-doped two-dimensional Hubbard model and show that the interlaced coarse-graining in combination with the extended DCA$^+$ algorithm permits the determination of the superconducting $T_c$ on cluster sizes for which the results can be fit with a Kosterlitz-Thouless scaling law.