Newton believed that there was an absolute spatial frame of reference:
Absolute space, in its own nature, without regard to anything external, remains always similar and immovable.
So as far as Newton was concerned, acceleration could always be detected relative to this absolute reference frame, because Newton's laws of motion would not hold in an accelerated reference frame (unless fictitious forces were introduced). So even in a universe with only two objects, it would always be clear which of them was being accelerated.
On the other hand, Newton's contemporary Leibniz believed that there was no absolute space, and that space only made sense as the relative location of bodies. So for Leibniz, Newton's laws of motion could only apply in a universe in which there were enough distant objects more or less stationary with respect to each other (the "fixed stars") to define an inertial frame of reference. In a two object universe Newton's laws of motion would not apply. If there was relative acceleration, both objects would see themselves as stationary and the other object as accelerating.
Ernst Mach expanded on Leibniz's point of view and encapsulated it in Mach's principle. He is reported to have said "When the subway jerks, it's the fixed stars that throw you down". Mach's thinking was a guiding factor in Einstein's development of general relativity.