What is the relationship between curved vs flat and Lorentzian vs Newtonian? Poisson's equation $\Delta \Phi = 4 \pi G \rho$ is not Poincare invariant, hence the need for a new theory of gravity after Special Relativity (SR). 
The motivation for gravity as curvature in General Relativity (GR) appears to have been the equivalence principle, which is true  in Newtonian gravity also. Indeed, the idea of gravity as curvature appears also as a reformulation (or perhaps mild generalisation) of Newtonian gravity called Newton-Cartan theory. 
Is there something about Lorentzian geometry and about curved geometry that makes the two play particularly well together as opposed to Newtonian geometry and curved geometry? 
Is gravity as curvature the best view of any theory satisfying the equivalence principle, regardless of whether the theory has Lorentzian or Newtonian geometry? 
 A: 
Is there something about Lorentzian geometry and about curved geometry that makes the two play particularly well together as opposed to Newtonian geometry and curved geometry?

Yes, the key facet of Lorentzian geometry that makes it good for geometrizing gravity is that it has a single metric for spacetime. As you mentioned, since it respects the equivalence principle, Newtonian gravity can also be geometrized as was shown in Newton-Cartan theory. However, the fit is not as natural and the chief symptom is that there is no longer a single spacetime metric, but rather a pair of degenerate metrics. In general relativity spacelike intervals and timelike intervals are different, but unified and treated on the same footing as particular values of the same metric. Not so in Newton-Cartan gravity where they are not unified at all. 

Is gravity as curvature the best view of any theory satisfying the equivalence principle, regardless of whether the theory has Lorentzian or Newtonian geometry?

“Best” is a judgement call, typically based on aesthetic or philosophical preferences. I don’t have a strong opinion. If pressured to provide an opinion I would generally prefer Newtonian gravity simply for practical ease of computation. What I can say is that as far as I know any theory of gravity which satisfies the equivalence principle can be geometrized. There may be perfectly valid reasons that doing so is not the “best” choice for a particular purpose. 
A: I discussed the issue of curved space-time geometry, in relation to Newtonian gravity, more fully in my reply here
Newtonian gravity as curvature of space
A key insight is that the symmetry group for non-relativistic theory is not the Galilei group, but its central extension the Bargmann group, and since the Bargmann group's natural geometric representation is 4+1 dimensional, then any theory of gravity that fully embodies Bargmann symmetry will reside on a 4+1 dimensional ambient geometry. For reference, the metric for the $N$-body problem in Newtonian gravity is given by the line element
$$dx^2 + dy^2 + dz^2 + 2 dt du - 2 V dt^2 = 0,$$
where $V$ is the gravitational potential per unit mass of the $N$ bodies. The constraint reduces the geometry to 4 dimensions, but with a metrical structure that is singular since it is on a light cone in the ambient geometry.
The flat geometry, where $V = 0$, is the Bargmann geometry, which carries the representation of the Bargmann group. In the reduced 3+1 dimensional geometry, the co-variant metric and contravariant metric are no longer inverses, but are independent. So, the geometry is a Klein geometry given by the following invariants:
$$dt^2, \hspace 1em \left(\frac{∂}{∂x}\right)^2 + \left(\frac{∂}{∂y}\right)^2 + \left(\frac{∂}{∂z}\right)^2, \hspace 1em dx \frac{∂}{∂x} + dy \frac{∂}{∂y} + dz \frac{∂}{∂z} + dt \frac{∂}{∂t}.$$
The Bargmann group is the inhomogeneous group which preserves each of these invariants. The metric is rank 1 and the dual metric is rank 3. Their contraction continues to be proportional to a multiple of the identity tensor (which corresponds to the third invariant listed), but that multiple is zero.
More generally, the issue of Bargmann structures in curved geometries is considered here in Physical Review D, Volume 31, Number 8, 15 April 1985, "Bargmann structures and Newton-Cartan theory", C. Duval, G. Burdet, H. P. Künzle and M. Perrin, which shows how the older "Newton-Cartan" theory may be embodied within and superseded by the 4+1-dimensional geometric formulation.
A key point worth raising, which gets to the core of your question, is what is mentioned in it at the start of the section "VI. Newton's Field Equations", where they write "Strangely enough, Newton's field equations [as listed in equations (1.15) and (1.17) in the paper] cannot be easily derived from a specific space-time Lagrangian density."
In my reply, I showed how the above-mentioned line element can be morphed into the Schwarzschild solution, for the case $N = 1$ of 1-body located at the origin of the coordinate grid. Together, they form a 1-parameter family of deformations ... with a parameter used in that place that is also the name of That Theme Song from the old Carl Sagan Cosmos. The zero value of the parameter gives you the non-relativistic formulation - Newtonian gravity - while the positive values of the parameter each give you the equivalent of the Schwarzschild geometry; embedded in an ambient 4+1 dimensional geometry.
No similar deformation is forthcoming that connects any Lagrangian density suitable for Einstein's theory of gravity with any Lagrangian density suitable for Newtonian gravity. That's the gap which the paper refers to.
A closer analysis of Poisson's equation shows partly where the gap arises from. In the ambient geometry, the mass density $ρ = ^4_5$ is actually the $(4,5)$ component of the stress tensor-density, where the coordinates are arranged as $\left(x^1, x^2, x^3, x^4, x^5\right) = (x, y, z, t, u)$. [Footnote: the natural form for the stress tensor density, which is associated with the transport equations for mass, energy and momentum, is as a rank (1,1) tensor density, not a rank 2 covariant tensor.] In contrast, the sole non-zero component for the densitized Einstein tensor $^ρ_ν = \sqrt{|g|} g^{ρμ} G_{μν}$ is the $(5,4)$ component $^5_4 = -∇^2 V$. (Another footnote: for the solutions I posed in the previous reply, $g = -1$, so tensor densities and tensors can be conflated, to some degree, but it's a big no-no in general.)
The lifting of the stress tensor for non-relativistic theory into a symmetric tensor over the ambient 4+1 dimensional geometry actually has a gap for the $(5,4)$ component, with nothing in either relativity or non-relativistic theory to inform us on what ought to go there. There is also the question of what the coupling coefficient for the field equations would be since there is no $c$ in non-relativistic theory and you only have $G$ available.
I've begun to suspect that there's more to this gap than meets the eye, and that the mismatch may inform us not only on the question of what larger and more comprehensive formulation for Newtonian gravity there should be, but also a larger and more comprehensive formulation for Einstein's gravity. To put it more directly: I think the gap shows that we have the wrong theory, even in the relativistic case, and that both it and its non-relativistic limit need to be lifted to something higher that possesses a "correspondence limit" that can be written as a family of deformations.
You will find other papers published by some or all of the above-mentioned authors that gravitate around related topics. There are also others who have given it air-play, like
"Curved non-relativistic spacetimes, Newtonian gravitation and massive matter",
https://arxiv.org/abs/1503.02682
Also qualifying, unbeknownst to the authors themselves, who accidentally stumbled onto the same topic area without realizing it, is:
"5D Generalized Inflationary Cosmology"
https://arxiv.org/abs/hep-th/9508120
The geometries they discuss are relativistic versions of the curved 5D-Bargmann geometries.
De Pietri et al. tried to confront the problem of Lagrangian formulations by gauging the Galilei group. I'm not sure if their "extended Galilei group" means "Bargmann group" or not.
Galilean Theories Of Gravitation
https://arxiv.org/abs/gr-qc/9212002
Standard and Generalized Newtonian Gravities as ``Gauge'' Theories of the Extended Galilei Group - I: The Standard Theory
https://arxiv.org/abs/gr-qc/9405046
Standard and Generalized Newtonian Gravities as ``Gauge'' Theories of  the Extended Galilei Group - II: Dynamical Three-Space Theories
https://arxiv.org/abs/gr-qc/9405047
This is the closest, that I am aware of, of anyone writing down an actual Lagrangian formulation for non-relativistic gravity. It is very involved, and I suspect it could be simplified if it is written in a 4+1-dimensional geometry.
