Is "non-inertial" frame a relative term? I've heard only two definitions of non-inertial frame so far:
I. A frame that is accelerating with respect to an inertial frame.
II. A frame where Newton's Laws are invalid.
Let's begin with definition I. We know that acceleration is a relative term. Let's say the universe consists of two sets of frames A={1,2,3...} and B={1',2',3'...} where the frames in A are not accelerating wrt each other and the same holds for frames in B but all frames in B have the same acceleration wrt the frames in A.
Now I claim A consists of inertial frames and Newton's are valid there. Then frames in B are non inertial by definition 1 and experiences a pseudo force.
What if my friend claims B consists of inertial frames? For him, the pseudo forces are real implying Newton's law are valid in his set of frames and it is actually my set of frames where Newton's laws are invalid. What is wrong with this line of thought?
The root conflict seems to be in the use of pseudo force. As stated in Goodman and Warner, "One might say that F = ma holds in any coordinate system provided the term 'force' is redefined to include the so-called 'reversed effective forces' or 'inertia forces'."
 A: Frames of reference are simply sets of coordinates used to label points and events in space and time. You can use any sets of coordinates you like, provided they allow points and events to be specified unambiguously. You could, if you wished, adopt a frame of reference with an origin that oscillated from side to side like a pendulum bob. You could then posit the existence of a pseudo force that acted upon everything in the universe, causing it to move from side to side with a fixed period.
You will run into difficulties, however, if you try to claim that pseudoforces are real. In the case of your frame B, for example, you would have to identify a real source of a force that was causing everyone in the Universe to be accelerating perpetually. You would have to account for a recoil of the source of the force, to account for the fact that the universe would impart an equal and opposite reaction to it. You would also have to explain how the acceleration could possibly continue at a constant rate forever and reconcile that with the experimentally proven facts about relativity. In summary, it would be nonsense.
A: Think about how whether or not a straight line on a sheet of paper isn't a relative term as on a sheet of paper a straight line is the shortest distance between two points.
Whether or not a path through space and time is a straight line is also not relative, although it's not always as simple as finding the shortest path between two points.  In the absence of Gravity, for two points that are separated more in time multiplied by the speed of light than in space, the straight line path between the two points is the longest path between the two points that does not involve moving faster than the speed of light.  Anything that moves slower than the speed of light and traces out a straight line path through spacetime is in an inertial reference frame.
A: First off, let me emphasize that there is no intrinsic connection between the qualifications 'inertial' and 'orthogonal'; those are independent qualifications.

To your actual question:
The qualifications 'non-inertial coordinate system' versus 'inertial coordinate system' arise from the phenomenon of inertia. The distinction between non-inertial and inertial can be made without ambiguity.
In a recent answer I discuss how the phenomenon of Inertia gives rise to the concept of the equivalence class of inertial coordinate systems


About the statement Goodman and Warner that you quote:
They are muddling the concept of force, which is a dead end.
The concept of 'force' is tied in with the concept of 'interaction'. (As in the 4 fundamental interactions of Nature.) The simplest instance of interaction is when two objects are interacting with each other, changing each others momentum. The minimum is a pair of objects, otherwise you have no way of meaningfully stating conservation of momentum.
Inertia cannot be put in the same category as force. Inertia is the phenomenon that a force is required to cause change of velocity. Inertia does not involve a pair of objects. Inertia is in a category of its own.
To use the expression 'pseudo force' for manifestation of inertia is muddling the waters in the extreme. Inertia is real, and it cannot be put in the category of force.

The only way to formulate a theory of motion at all is to take inertia as the prime organizing principle.
Example:
the case of using a rotating coordinate system.
If you use a coordinate system that is rotating at a constant angular velocity you add a centrifugal term and a coriolis term to the equation of motion. The centrifugal term and the coriolis term contain the angular velocity of the rotating coordinate system with respect to the inertial coordinate system. That is: the  equation is still using the inertial coordinate system as the underlying reference.
What Goodman and Warner are suggesting is comparable to this:
"One might say that the circumference of a circle is 6, provided $\pi$ is redefined as having a value of 3".
A: We can tell the difference between inertial forces and real forces because an inertial force affects every object in direct proportion to its mass; a real force only affects the object on which it is exerted. If we have to create inertial forces to satisfy $F=ma$ then we know we are working in a non-inertial frame. So there is an asymmetry between inertial and non-inertial frames, and acceleration is absolute, not relative.
And, yes, this means that in general relativity gravity is an inertial force too.
A: 
What if my friend claims B consists of inertial frames?

Then your friend is lying. His statement is inconsistent with the previous statements. Since, the A set of frames and B set of frames are accelerating relative to each other, they cant BOTH be inertial frames ( i am assuming, this example takes place in a flat region of spacetime ) . At most one of those set, can be inertial frames.
