Recent work highlights that tens of Galactic double neutron stars are likely to be detectable in the millihertz band of the space-based gravitational-wave observatory, LISA. Kyutoku and Nishino point out that some of these binaries might be detectable as radio pulsars using the Square Kilometer Array (SKA). We point out that the joint LISA+SKA detection of a $f_text{gw}gtrsim$1 mHz binary, corresponding to a binary period of $lesssim$400 s, would enable precision measurements of ultra-relativistic phenomena. We show that, given plausible assumptions, multi-messenger observations of ultra-relativistic binaries can be used to constrain the neutron star equation of state with remarkable fidelity. It may be possible to measure the mass-radius relation with a precision of $approx$0.2% after 10 yr of observations with the SKA. Such a measurement would be roughly an order of magnitude more precise than possible with other proposed observations. We summarize some of the other remarkable science made possible with multi-messenger observations of millihertz binaries, and discuss the prospects for the detection of such objects.