Are Newtonian forces real forces or just a useful construct? I am new to physics but not new to science/scientific thinking.
Since I was young I have never really understood how to interpret the Newtonian forces. In some cases they seem very real. E.g. the static friction force can be nicely explained as gluing of atoms, or something like that.
But if you consider two objects of different weights on the same table, then the table applies 2 different normal forces to the 2 objects. This really seems to be an abstract construct. We see that the objects are not moving so to be self-consistent with this massive framework of forces we are building we are claiming that the table is exerting a force towards the object. Yeah sure!  What kind of atomic interpretation could this have?
Of course, it does work at the end, so I could totally accept the "construct" interpretation, since it's a useful model anyway. But what transpires from reading articles etc. is that Newtonian forces are "more" than that. They are actually "real".
So, what is the right way to conceptualize the Newtonian forces?
I hope I expressed my confusion clearly.
 A: 
We see that the objects are not moving so to be self-consistent with
this massive framework of forces we are building we are claiming that
the table is exerting a force towards the object.. Yeah sure! What
kind of atomic interpretation could this have?

Everything we see around us is made of atoms (mostly organised in molecules) In turn, atoms consist of a tiny, positively charged nucleus surrounded by a much, much larger negatively charged electron cloud.
All electrons are negatively charged and negatively charged objects repell each other by the Coulombic force.
This is what physically underpins the force and reaction force when a massive object sits motionlessly on a table (e.g.): the electron clouds of the atoms making up the table and the electron clouds of the atoms making up the massive object repell each other.
As an interesting aside this also means that the table and object never really touch and that the object kind of hovers a very small distance above the table's surface.
A: Yeah it’s a good question. Clear. And not new at all.
This is a philosophy of science topic.
Summary
The interesting question is whether any physics theory could even be true - hotly debated in philosophy of science as discussed below. Theories usually introduce mechanisms and notions about physical reality on top of their predictions.
Secondly, showing it will never be falsified is not only impossible, but we can’t even claim to have high confidence. We continue to get better at both measuring and at creating extreme conditions, and we have observed other theories fail under new conditions. There are even theories that the laws of physics vary through space and time. One example is bubble universes, and another is inflation.

The meaning of “a true theory”
Assume we somehow can show it will never face a direct counter-example. We’d still need to know what it means for a theory to be true. In logic, “A” is the same as “A is true”. But for physics, some (e.g. below) say predictive capacity is not the same as true representation.
For example, electric fields are used extensively, but we do not know that they exist per se, nor whether the question even has meaning. We know charges exert forces by Coulombs Law. That is indisputable and arguably primary. An infinite variety of charge distributions can result in a certain net force on a unit charge at a point. For tractability, the magnitude of an electric field at that point expresses the same information.
So the question is whether Maxwell’s equations are “true”. If we say that electric fields are real and that theories using them as primitives are “true”, then what about electric potential? That’s the energy in this field that we now say exists. Does that exist? Potential is the energy (as work) it would take to bring a unit-charge to that location. These and other questions are debated in philosophy of science - as is the whole notion of physical theories and truth.
The same type of thinking applies to gravity. From Forces and Fields by Mary B Hesse

There is a physical difference between a gravitational field ... and the velocity field of a fluid. In the latter case the field function is an actual property of material at every point of the field, but in the gravitational case the potential function V is 'potential' in the sense that it does not necessarily describe a material property of the field ... it describes a potential property, namely, the force that would be exerted if a small mass were introduced into the field at that point.

Despite her claim that the case is simpler, debate has sprung up about the reality of the stream function. We would at least need one fluid particle to travel the entire streamline for it to be real. As hydrodynamics has advanced, the shape of the water molecule itself is being taken into account, such as here: https://pubs.acs.org/doi/10.1021/acs.jpcb.6b01012
( The basics of including molecular dynamics into hydrodynamics: https://www.redlandsusd.net/site/handlers/filedownload.ashx?moduleinstanceid=16224&dataid=10931&FileName=Water%20Properties%20Activity.pdf
No particle follows the streamline: I would say that means we have realized streamlines don’t actually exist - depending again on what we mean by existing, even though models using them do work.
A: First we must see how normal force is applied
When we place a block on a table  the table under it actually deforms. The deformation is so small that it can't be observed and we simply neglect it. As soon as we place block on the table it pushes / deforms table which develops restoring forces.
These restoring forces are electromagnetic in nature and when weight of block equals these forces, it is at rest on table.These restoring forces sum up together as what we know as Normal force
If you take a heavier block it will deform table more than a lighter block and therefore more restoring forces will be developed i.e. more normal reaction exerted.
A: Force is at first a subjective feeling. It can be related for example to the effort to overcome friction to move an object across a surface, as you mentioned. We can say that a force is bigger or smaller than another within a certain range, but even then, we can not say how much a bigger force is greater than a smaller one.
So, the issue is how to quantify it. This job is done by load cells or strain gages, that rely on the proportionality between force and displacement. On the other hand, that devices can be calibrated to match the property that the weight is proportional to the mass, and doubling the volume of the same material, its weight must also double.
In the example of objects in a table, even if they are so heavy that we can not move them, and our subjective notion of force is useless, a load cell can say precisely the normal force from the table on each of them.
A: 
we are claiming that the table is exerting a force towards the object. Yeah sure! What kind of atomic interpretation could this have?

There is no "interpretation" here. The force you are looking for is one of the 4 fundamental forces of the universe: the electromagnetic force, and you are quite familiar with it.
This force governs almost all everyday physical interactions except gravity-based ones. This means all possible effects, phenomena, movements etc. including keeping atoms, molecules and whole bodies together, all motion that's not caused by gravity, everything going on in liquids, gases etc., everything having to do with pressure. It is based on charges which repel or attract each other.
In your example, if you put an apple over a table, gravity pulls it down towards the table. As soon as the atoms which make up the apple get close enough to the atoms of the table, repulsion (of the electron hulls of the atoms in the separate objects) and attraction (of the atoms/molecules within the same object) lead to the apple basically floating over the table, in some sense. The gory details are complicated, but if it interest you, you can go down a rabbit hole of intermolecular forces or intramolecular forces. These are all non-fundamental, secondary forces "created" by electromagnetic effects.
In fact, depending on which physicist you ask, objects never touch at all (see this video for a very entertaining demonstration), but all discrete objects float next to each other, attracted and repelled by a combination gravity and electromagnetism.
So in this case, the force of gravity pulls down, the force created by electromagnetism pushes up, and when they are equal, the net overall force equals zero, at which point Newton's First Law kicks in and makes sure that the apple stays where it is.
This aspect of the electromagnetic force is a bit hard do "feel" for us, but all other motions you see in everyday life are based on it too. Some easily accessible are for example magnets, or statically charged hair which stands up (or even follows your hand if you move it over their head). Obviously these seem quite different from a force which keeps objects from penetrating each other, but at the end of the day it's the same. Charged objects creating electromagnetic fields, attracting and repelling.
As mentioned in the comments, there is of course a lot of other stuff going on, e.g. the Pauli Exclusion Principle, but I would like to focus on the electromagnetic force as I find it quite fascinating how a lot of things we see can explained with it alone - from the atomar level to galaxies spewing out streams of matters...
A: 
But if you consider two objects of different weights on the same table, then the table applies 2 different normal forces to the 2 objects. This really seems to be an abstract construct.

There is nothing abstract or artificial about it. Or at least nothing more abstract than the other forces you mentioned as being acceptable.
Consider that the surface of the table is covered in many small springs. From Hooke’s law you know that the force from a spring is proportional to the compression of the spring.
Now, if you look at the springs you will notice that the ones under the heavier object are compressed more than the ones under the lighter object. There is no mystery where the additional force comes from, it comes from the additional compression of the springs.
The same thing happens on a real table, but the springs are microscopic. But even though you cannot visibly see the compression of the tabletop it is there and sensitive instruments can measure it.
A: 
But if you consider two objects of different weights on the same table, then the table applies 2 different normal forces to the 2 objects. This really seems to be an abstract construct. We see that the objects are not moving so to be self-consistent with this massive framework of forces we are building we are claiming that the table is exerting a force towards the object. Yeah sure! What kind of atomic interpretation could this have?
Of course, it does work at the end, so I could totally accept the "construct" interpretation, since it's a useful model anyway. But what transpires from reading articles etc. is that Newtonian forces are "more" than that. They are actually "real".

You're looking at this the wrong way. Newton's laws are simply a part of how we can understand mechanics, it has no relation to what is 'real'.
It is important to distinguish a model and what it predicts from what is real in itself.
This can be emphasized by noticing that there are either ways to arrive at the dynamical laws. For instance, we can derive the differential equations governing dynamics of a system starting from a completely different conceptual view point of considering energies (lagrangian and Hamiltonian mechanics).
Now, on top of that to give a more sophisticated interpretation of why the model works on a deeper level is the goal of physics.
A simple example I learned of the above idea in high school was of the kinetic gas theory. We know the internal energy of an ideal gas is solely a function of temperature, but an interpretation to it is not there in thermodynamics.
To give one, we use kinetic gas theory where we find the the temperature is related to how fast the molecules are bouncing around in a container.
A: "But if you consider two objects of different weights on the same table, then the table applies 2 different normal forces to the 2 objects. This really seems to be an abstract construct."
Suppose that you placed the objects, not on a table, but on a big block of squashy foam rubber. The foam rubber would support them both, would it not? So the block would provide each object with an upward force equal to its own weight. How it does so is not mysterious: the more the block is deformed by the object the more the force that is needed to do so, and the more the (equal and opposite) force that the block exerts on the object. So by sinking deeply enough, even the heavier object will receive the upward force that it needs to balance its weight!
What has this to do with objects resting on a table? Everything. The table is deformed enough by each object to support that object. The table is not perfectly rigid, though very much more rigid than the foam rubber, so you probably don't see the deformation.
I implied that the more the table is deformed by the object the more the force that is needed to do so. This can be traced to the force between atoms. They have a natural equilibrium separation, when there is no net force between them. But push them closer together than this and they repel each other. The closer you push them together the greater the repulsive force. [One way of explaining this is that there is a negatively charged electron cloud between the positively charged nuclei, but when you push the nuclei closer together you push some of the electron cloud out of the way, so that the nuclei are less shielded from each other's repulsive force.]
Oh: I almost forgot... Are Newtonian forces real force or just a useful construct? Well they're certainly the latter: they are hugely successful in what they can explain and predict. Are they real? This question can be asked about every concept in Physics and beyond. It is a metaphysical question. Literally it is beyond Physics.
A: This is really more of a philosophical question than a physics question.
Most physics doesn't actually explain "reality". Physical laws are all just models that can be used to predict phenomena, generally using mathematical methods. Some of these models have more precision, operate at finer levels of granularity, or cover a wider range of conditions more accurately.
So quantum mechanics isn't any more real than Newtonian mechanics, it just describes things more precisely. For macroscopic objects, they both produce the same results. So unless you're dealing with objects at atomic scales, Newtonian forces are "real enough".
Similarly, Newton's Laws of Motion are perfectly fine models of reality in conditions that we normally experience. You need to resort to Special Relativity at high speeds, and General Relativity in extreme gravitational fields. The latter may be considered "better" because they cover wider ranges, and Newton's Laws fall of them out as an approximation in specific cases. But that doesn't make them any more "real".
So everything that physicists discovers is just "useful constructs" that describe what we see, either in real life or their experiments . Some are just more useful in different contexts -- Newton's Laws are fine for explaining an apple falling from a tree, but not the results of a particle collider.
A: At least some aspects of force are just a convention. This is about labels and interpretation, not physical predictions. For instance Jammer's book Concepts of force (2011) has a chapter "Modern criticism of the concept", though my following examples are not taken from there.
One example is gravity is considered a force in Newton's gravity, but not in Einstein's gravity (general relativity). In Newtonian concepts, gravity exerts a downward force on your masses, but the table gives an upward force, so the sum of forces is zero and there is no motion. In the relativistic context, gravity is not called a "force", rather the masses want to fall freely, which would be a straight line in spacetime, but the table exerts an upward force to stop this. Hence there is a net upward force, and this prevents freefall. This is just a guess, but when you formulate Newton's gravity using curved spacetime like in relativity (Newton-Cartan theory), perhaps gravity is no longer interpreted as a force there.
Similarly, there are two definitions which appear in relativity textbooks:
$$f = m\frac{d\vec v}{dt}\qquad\textrm{or}\qquad f = \frac{d}{dt}(m\vec v).$$
These are not the same if the mass $m$ is not constant. In relativity the velocity $\vec v$ is a 4-dimensional vector, but perhaps parts of this example could also apply Newtonian physics.(?) Anyway Steane (2012, $\S2.5.5$) has an excellent description:

...We are free to choose either, because the relation is a definition of 4-force, and we can define things how we wish. However, some definitions are more useful than others...

The difference comes down to whether we call a change in the rest mass of an object a "force". For example, if I heat up one of your objects, it gains energy and hence mass. But I did not push it around through space. So was it a "force"? If you choose "yes", it is called a "thermal force", in contrast to a "pure force". This corresponds to the second definition above, and is the better one, as Steane also concludes.
