Interplanetary missions have typically relied on Radio Science (RS) to recover gravity fields by detecting their signatures on the spacecraft trajectory. The weak gravitational fields of small bodies, coupled with the prominent influence of confounding accelerations, hinder the efficacy of this method. Meanwhile, quantum sensors based on Cold Atom Interferometry (CAI) have demonstrated absolute measurements with inherent stability and repeatability, reaching the utmost accuracy in microgravity. This work addresses the potential of CAI-based Gradiometry (CG) as a means to strengthen the RS gravity experiment for small-body missions. Phobos represents an ideal science case as astronomic observations and recent flybys have conferred enough information to define a robust orbiting strategy, whilst promoting studies linking its geodetic observables to its origin. A covariance analysis was adopted to evaluate the contribution of RS and CG in the gravity field solution, for a coupled Phobos-spacecraft state estimation incorporating one week of data. The favourable observational geometry and the small characteristic period of the gravity signal add to the competitiveness of Doppler observables. Provided that empirical accelerations can be modelled below the nm/s ² level, RS is able to infer the 6 × 6 spherical harmonic spectrum to an accuracy of 0.1–1% with respect to the homogeneous interior values. If this correlates to a density anomaly beneath the Stickney crater, RS would suffice to constrain Phobos’ origin. Yet, in event of a rubble pile or icy moon interior (or a combination thereof) CG remains imperative, enabling an accuracy below 0.1% for most of the 10 × 10 spectrum. Nevertheless, technological advancements will be needed to alleviate the current logistical challenges associated with CG operation. This work also reflects on the sensitivity of the candidate orbits with regard to dynamical model uncertainties, which are common in small-body environments. This brings confidence in the applicability of the identified geodetic estimation strategy for missions targeting other moons, particularly those of the giant planets, which are targets for robotic exploration in the coming decades.