The value of force exerted on both by the Earth is not the same, and the value of their accelerations is not the same. If you make the equations you will see that Newton's second law definitely holds true in this case.
I believe you are confused because you thought that the acceleration of a body towards the Earth is always equal to 'g', but this is not the case. The value of gravitational acceleration is g only for bodies that are close to the surface of the Earth. To get an idea of this let me give you some formulae. For an exact measurement of the acceleration varying with height we can use:
For a body of mass m at a height h from the surface of the Earth having a mass M and radius R,
$$
F = \frac{GMm}{(R+h)^2}
\\
a = \frac{F}{m}
\\
a = \frac{GM}{(R+h)^2}
$$
We also sometimes use an approximation for smaller heights (in comparison to radius of the Earth):
We have,
$$
a = \frac{GM}{(R+h)^2}\\
\implies a = (GM)(R+h)^{-2}\\
\implies a = \frac{GM}{R^2} [1 + \frac{h}{R}]^{-2}
$$
We can use binomial approximation on this, which gives us:
Since $h << R$,
$$
a = \frac{GM}{R^2} [1 - \frac{2h}{R}]
$$
since we know that $g = \frac{GM}{R^2}$, we can substitute this to get,
$$
a = g_{height=h} = g [1 - \frac{2h}{R}]
$$
Hope this clears your confusion!