Measuring neutrino interactions with matter is arduous but rewarding. To date, experiments have measured the neutrino-nucleon cross section in the MeV-PeV range, using terrestrial and astrophysical neutrinos. We endeavor to push that measurement to the EeV scale, in order to test competing expectations of the deep structure of nucleons and possibly reveal new neutrino interactions. Cosmogenic neutrinos, long-sought but still undiscovered, provide the only feasible way forward. However, because their flux is low, they have evaded detection so far. Fortunately, upcoming in-ice radio-detection neutrino telescopes, like RNO-G and the radio component of IceCube-Gen2, have a real chance of discovering them in the next 10-20 years. In preparation, we perform the first detailed study of their sensitivity to the deep-inelastic-scattering neutrino-nucleon cross section at EeV energies, extracted from the attenuation of the cosmogenic neutrino flux as it traverses the Earth across different directions. We use up-to-date predictions and tools at every step: in the flux of cosmogenic neutrinos---predicted using recent ultra-high-energy cosmic-ray measurements---in their propagation inside the Earth---computed using leading and sub-leading neutrino interactions---and in their detection in radio-based neutrino telescopes---based on advanced simulated detector responses.