The shoe has more mass than the coin, so it takes more force to accelerate the shoe than it does the coin. The two effects (more force needed to accelerate heavier object, and force of gravity on heavier object is greater) exactly balance out.
Mathematically, you can write down the equation for the acceleration of an object of mass m being accelerated by a force F: [itex]F=ma[/itex] and the the equation for the force of the Earth's gravity acting on that same mass m: [itex]F=\frac{mGM_e}{r^2}[/itex] where [itex]M_e[/itex] is the mass of the Earth and G is the gravitational context, do some algebra, and you'll end up with a value of a that is independent of m.