We know that the electrostatic force between two charges depends on the medium between the charges and its permittivity. Why, then, doesn't the gravitational force depend on the medium?
Electrodynamics in Vacuum does not have a medium-dependence - as does gravity. If we do introduce a medium, we end up in a continuum theory of chargeable or polarisable media, which is where the permittivity comes from (for anyone not familiar with this, I would recommend reading a bit of Jackson's Electrodynamics). In gravity, there is no such thing as polarisation or charges of media, thus no need to include continuum effects (as far as I know, GR is not my forte).
The permittivity of the medium between two electric charges affects their electrostatic interaction because the medium can become polarized: that is, the medium has lots of neutral atoms inside it, and in each of those atoms the positive and negative charges shift to create a tiny dipole, and in the process they create thin layers of positive and negative net charges at the surfaces of the medium facing the original charges, where there's no adjacent atoms of the medium to cancel out the outward-facing parts of the last atoms. These surface charge layers then affect the electrostatic interactions between the original charges.
In gravity, on the other hand, there simply isn't a negative mass with an attractive gravitational interaction to normal matter, so the atoms in the medium cannot form gravitational dipoles (they can only shift positions) and they cannot form surface layers of gravity-cancelling 'negative mass'. Since that mechanism is no longer present, its simplified manifestation (i.e. the medium's permittivity) is also gone.