How does the earth bring down a falling object's velocity to zero on contact?
If the normal force on an object from a horizontal surface is equal to the weight of the object, the object could never be decelerated because the net force would go to zero as soon as it touches the surface as it would then keep moving into the surface at constant speed.
The object is pushing into the earth due to its non-zero velocity, exerting more than the usual force of gravity on the earth, so the reaction force on the object is larger than just the force of gravity for non-zero velocity. This decelerates the object until its velocity is zero, and the reaction force on the object is just the normal force counteracting gravity.
It doesn't happen spontaneously on contact, but it usually happens rather fast - unless the earth is so soft at the impact spot that the object can bury into the ground.
The source of the force the earth exerts on the moving object is due to the earth resisting the object moving into it. Two solid objects cannot occupy "the same space", and when one is moving such that it would end up inside the other, the other resists by exerting force. The origin of that force is Pauli exclusion and electromagnetic repulsion between the electrons of the atoms that constitute the two solids. For a more detailed discussion on why things can't move into each other, see Why doesn't matter pass through other matter if atoms are 99.999% empty space?
The normal force isn't instantaneous, it just happens in a very short time interval. At the exact moment an object hits the ground, the normal force is zero and only the atoms that are near the contact point experience a normal force and slow down. This miniscule normal force is caused by the repulsion of electrons around the atoms. Most of the object will keep moving like nothing happened. After a short time the atoms slightly above the contact point will bump into the atoms at the contact point, the contact point now acts as the ground and the same happens.
So the impact travels as a wave through the object and the further the wave travels, the bigger the total normal force will be. As long as the object has momentum/atoms that move down, the normal force will increase since downwards movement compresses the object, making the atoms repel eachother.
You're completely right that if $F_{normal}=-F_g$ the object keeps moving, but the normal force will keep increasing after that point until all its momentum is gone. At that point all its energy is stored in compression/deformation of the object. That energy is either converted to heat or back into momentum in which case the object bounces back up.
So during a bounce $F_{normal}$ will vary greatly and $F_{normal}=-F_g$ is only useful when the object is resting on the surface.
It might be easiest to imagine a spring between the object and the earth (representing elastic properties of matter).
When the object falls and first hits the spring, it will feel no force and the spring will start to be compressed. As the object compresses the spring further, it will start to feel a reaction force. In the case of a perfectly elastic collision, the object will stop when all its kinetic and potential energy have been converted to elastic energy stored in the spring. If we ignore the additional potential energy due to the change in height as the spring compresses, the math is very simple:
$$\frac12 m v^2 = \frac 12 k x^2$$
The force experienced by the object at full compression is then $kx$, which is
$$F = kx = \sqrt{kmv^2}$$
From this you can see that if the velocity is greater, or the elastic constant is greater (stiffer spring), the maximum force is greater. This is consistent with the idea that if you drop an object on a soft surface (an egg into a box full of feathers) the maximum force will be small (the egg won't break), but dropping the object on a hard surface (large $k$), the maximum force is greater (the egg will break).
We can add friction to the analysis, but the underlying principle is the same: any surface, when distorted, will present some kind of retarding force to the object impacting it. And as long as that force is greater than the weight of the object, it will reduce the momentum of the object until it comes to rest.
