Why does electric force depend on the medium?

First remember that $k = \dfrac {1}{4 \pi \epsilon_r\epsilon_o}$ where $\epsilon_r \ge 1$

It is because a medium can be polarised by an external E-field.
The dipoles so set up produce the external E-field produce an E-field in the opposite direction so the net E-field (the sum of the external and dipole produced E-fields) is smaller.
Thus the force a given charge is smaller.

A metal is "perfect" at negating the external E-field, so much so that the E-field in a metal is zero.

In electromagnetism there are both positive and negative charges. Hence the force due to electric charges can be attractive or repulsive. Gravity, when treated as a classical force field, can only be attractive, there are not two types of "gravitational charge".

What this means is that in electromagnetism, a given medium, may contain both positive and negative charges and these can be separated by the application of an electric field - a process called polarisation. The separation of the electric charges produces an electric field that when summed with the applied electric field leads to a different net electric field in the medium and thus a different force acting on a test charge in the medium.

Since there is only one type of "gravitational charge", this phenomenon does not occur when applying a gravitational field.