Interplanetary missions have relied on Radio Science (RS) for recovering gravity fields via detecting their signature on the spacecraft’s trajectory. Yet 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 an 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 geodesic observables to its origin. A covariance analysis was adopted to evaluate the contribution of RS and CG in the gravity field solution, for a mission duration of one week. 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/s2 level, RS is able to infer the 6x6 spherical harmonic spectrum to an accuracy of 0.1-1% w.r.t. the homogeneous interior values. If this correlates to a density anomaly beneath the Stickney crater, RS would suce 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 10x10 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 regards 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.