Your first explanation is based on observations of the stuff of ordinary life. Stuff is, in general, springy. Push on it, it pushes back. If it's really springy stuff, then it moves a lot when you push on it a little. If it's really stiff stuff, then it moves a little even if you push on it a lot. But all stuff is observed to be springy.
This interaction between pushing and springing back is the macroscopic behavior of stuff.
Your second explanation is based on a deeper understanding of what stuff is made of -- to wit, all normal stuff that we might stuff our finger into is made of really little stuff called atoms which interact with each other primarily through the electric field and the behavior of electrons, which themselves interact with the atomic nuclei through the electric field.
Your finger is made of stuff, which is made of atoms, the outermost parts of which is electrons. If you find something to push on, that will, inevitably, be made out of stuff that's made out of atoms, the outermost parts of which are electrons (unless you've stumbled onto some antimatter, in which case your experiment is about to end catastrophically).
When you push on the stuff, the electrons on the atoms on the surface of the stuff are repelled by the electrons on the atoms on the surface of your finger -- and that's what causes the normal force. It's the same thing as in the first example, it's just that in the first example we're modeling the stuff as, well, "just stuff", while in the second case we've asked "yes, but why?" enough time that we're down to discussing just how unfriendly electrons can be toward each other when you attempt forced marriage of their favorite atoms.
Note that if you do this experiment right after putting a drop of super glue on the stuff, you'll find that the normal force can change sign, much to your consternation if you were expecting it to only be positive, or zero (if you try this, don't freak out when you have stuff glued to your finger -- your skin if constantly exuding oil and shedding its outer layers -- just wait a few hours, and you'll peel right off of the stuff). What you've done is chemically bonded your skin to the stuff, via the action of electrons on the outermost layers of the stuff, your skin, and the glue.
Which relates to your next two questions.
The reason that stuff occurs as solids (or even liquids, for that matter), is because electrons, in addition to making atoms repel each other, will also make them attract each other over very short distances. Solid stuff is made of atoms that are in deep and committed relationships. At the macro level, we say "stuff deforms and pushes back". At the atoms-and-electrons level, when stuff deforms, atoms are being pulled further away from each other than they'd like (tension), pushed closer together to each other than they'd like (compression), or being asked to slide in relation to each other (shear). All of these movement-vs-force interactions happen because the electrons and atomic nuclei have preferred positions, and when they resist being moved out of these preferred positions it's electric fields that are generating the forces.
Your third question is kind of unrelated to the first two -- yes, normal force is due, at the macro level, to deformation (or deformation is due to the normal force -- take your pick).
But I believe your confusion is that the two statements that you lead with are both describing the same phenomenon -- just at different scales.