I've got the NE and SW coordinates/points for a minimum bounding rectangle. How do I calculate the center point of this rectangle?
At first thought, I could calculate this using simple division. However, would that be right considering the (by now accepted) fact that the earth is not flat?
First off, note that the the term “rectangle” is not well defined if you actually consider the spherical case. There are no spherical quadrilaterals with geodesic edges and four right angles, although small quadrilaterals can come close. I guess that you have a bounding box in mind which comes from the extrema of the latitudes and longitudes of some data points. Your Wikipedia link supports that notion. In that case, the northern and southern boundaries would probably best be considered as circles of latitude, not great circle geodesics. In the sense of spherical geometry, these lines would not be considered straight. But then you'd get right angles, as Jyrki pointed out in a comment.
If you add latitudes and divide them by two, and also add longitudes and divide them by two, you will end up at a point which has equal distance to the western and the eastern boundary, and also to the northern and the southern boundary, at least if you consider circles of latitude for the latter. So that is a fair definition of what could be considered a center. You should make sure to avoid wrap-over problems, close to the $180°$ meridian or the poles, but that's just details.
There are however other reasonable but different definitions. For example, you could consider the circumcircle of the four corners, and treat its center as the center of the “rectangle”. Or you could consider the center of gravity of the surface area of the quadrilateral, projected back onto the sphere. So this very much depends on what properties you expect your center to have, and what definition you apply for your “rectangle”.
For small scales, all of this becomes irrelevant, since the differences become negligible.