Newton’s laws hold, provided we included the force of gravity, which according to us plays the same role as an apparent force would play in any other non-inertial reference frame
That is precisely the matter. To add a fictitious force is to modify Newton's second law according to $$\mathbf{F} + \mathbf{F}_{\text{fic}} = m \mathbf{a}.$$ Hence, you can view Newtonian gravity as either a force or a fictitious force, and the equations will be the same nonetheless.
The problem is more difficult once we move to Einstein's gravity. This time, we also need to take into consideration that massless particles, for example, experiment gravity. Such particles can't be described within the framework of Classical Mechanics and forces, and a simple argument in this sense is that Newton's Law would become $\mathbf{F} = \mathbf{0}$. We see then that something is failing in the description.
Within Special Relativity, I'm quite certain it would be possible to formulate gravity as some sort of force between particles. Newton's Second Law would be written
$$\frac{\textrm{d}^2x^{\mu}}{\textrm{d}\tau^2} + \sum_{\nu, \sigma} \Gamma^\mu{}_{\nu\sigma}\frac{\textrm{d}x^{\nu}}{\textrm{d}\tau}\frac{\textrm{d}x^{\sigma}}{\textrm{d}\tau} = 0,$$
which is known as the geodesic equation and describes the motions of particles in curved spacetime. However, this is not a convenient description. In particular because Special Relativity enforces that nothing can go faster than light and, as a consequence, one gets a deep relation between how light moves and causality. In other words, the way light moves determines which events in spacetime can influence which events. To understand these features of the theory in terms of forces would be quite complicated, but it becomes quite natural if we see gravity as a geometric effect rather than a force. Furthermore, I believe thinking in terms of forces would also make it very difficult to understand how the electromagnetic field interacts with gravity in contexts more general than just a light particle moving around.
It is important to notice that there are usually many ways one can describe a theory mathematically, but it does not mean all of them are simple, or convenient. For example, one could argue that the other planets orbit around the Earth, provided we include the effects of epicycles, and there would be nothing wrong with that description. In fact, this description was more accurate than Copernicus' description of circular orbits around the Sun. Nevertheless, understanding the movement of planets in terms of an inverse square law force eventually proved to be simpler than to consider the effects of many epicycles.
In Physics, we usually aim for the simpler possible description, in accordance with Occam's razor. For Newtonian Physics, it is easier to work with forces, and that is why every Physics 101 class will discuss gravity in these terms. Nevertheless, once problems get more complex, differential geometry becomes more convenient than descriptions in terms of forces.
