Why does electric force depend on the medium? Comparing the equations for the gravitational and electric force 
$$\vec{F}_g=-\frac{Gm_1m_2}{r^2}$$
and
$$\vec{F}_e=\frac{Kq_1q_2}{r^2}$$
I noticed the only major difference between them is that the constant $K$ depends on the medium. Why does it? 
 A: 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.
A: 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.
