El valor de la fuerza ejercida sobre ambos por la Tierra no es el mismo, y el valor de sus aceleraciones no es el mismo. Si haces las ecuaciones verás que la segunda ley de Newton se cumple definitivamente en este caso.
Creo que estás confundido porque pensabas que la aceleración de un cuerpo hacia la Tierra es siempre igual a "g", pero no es así. El valor de la aceleración gravitatoria es g sólo para los cuerpos que están cerca de la superficie de la Tierra. Para que te hagas una idea, te voy a dar algunas fórmulas. Para una medida exacta de la aceleración que varía con la altura podemos utilizar
Para un cuerpo de masa m a una altura h de la superficie de la Tierra que tiene una masa M y un radio R,
$$ F = \frac{GMm}{(R+h)^2} \\ a = \frac{F}{m} \\ a = \frac{GM}{(R+h)^2} $$
También utilizamos a veces una aproximación para alturas menores (en comparación con el radio de la Tierra): Tenemos, $$ a = \frac{GM}{(R+h)^2}\\ \implies a = (GM)(R+h)^{-2}\\ \implies a = \frac{GM}{R^2} [1 + \frac{h}{R}]^{-2} $$ Podemos utilizar la aproximación binomial en esto, lo que nos da:
Desde $h << R$ , $$ a = \frac{GM}{R^2} [1 - \frac{2h}{R}] $$ ya que sabemos que $g = \frac{GM}{R^2}$ podemos sustituir esto para obtener, $$ a = g_{height=h} = g [1 - \frac{2h}{R}] $$ Espero que esto aclare su confusión.