Computer Science Shows the Existence of Reference Frames as a Natural Consequence of Grouping Systems
Since you say you come from a computer science background, it is worth noting that every simulation that allows for nesting moving objects creates  reference frames. Let's look at this problem just like a computer simulation operating in a cardigan space.  To make this as simple as possible, let's say your simulation is 2 dimensional. If you've ever built a game engine from the ground up, you know that all objects in your game space need as a very minimum a position, velocity, and acceleration for each dimension so that each simulation cycle can determine how far the object moves.
So, to say all things are governed by the same set of physics is like saying we are all created from the same object class:
class thing {  
  float posX; 
  float posY; 
  float velX; 
  float velY; 
  set(float pX, float pY, float vX, float vY){ // Set initial position and velocity. 
    posX = pX; 
    posY = pY; 
    velX = vX; 
    velY = vY;  
  }
  void move(float aX, float aY) { // Apply acceleration each cycle based on outside forces.
    velX += aX;
    velY += aY; 
    posX = velX;
    posY = velY;
    cout "("<< posX<<","<<posY<<")";
  }
}   
Every object in your cardigan space follows the same variables and move function meaning they are controlled by the same set of physics.
Now let's see what happens when we move two objects in parallel:
thing object1 = (0,0,10,0);
thing object2 = (5,0,10,0);
for (int i = 0; i < 3; i++) {
  object1.move;
  object2.move;
  cout "\n";
}
This will output:
(0,0)(5,0)
(10,0)(15,0)
(20,0)(25,0)
However, there is another way to think about two objects moving in parallel like this, and that is by nesting your objects recursively.
thing group = (0,0,10,0)
group.thing object1 = (0,0,0,0);
group.thing object2 = (5,0,0,0);
for (int i = 0; i < 3; i++) {
  group.move;
  cout "\n";
} 
Here you get the same output by applying the motion to the group of objects as you did when you were applying the motion individually.  This means that group here is your reference frame because as far as object1 and object2 are concerned, they are both staying still; so, if you apply an acceleration to object1, its motion relative to object2 is the same as if they were staying still, or if they have an underlying acceleration/velocity being applied by the group.
So, basically, all reference frames are is a way you can mathematically take many particles, find 1 velocity and acceleration they all have in common, and treat their physics as a group instead of as individual objects.  This works because the objects all inherit the same common set of inputs from the object, and then just add/subtract their own local movements to it.
The difference between a computer and physics is that with a computer, there is a guaranteed top-level object with a fixed coordinate system, and each recursive layer is a fixed part of your data structure, but in physics, there is not necessarily a fixed data structure as far as anyone can prove. We just fit our mathematic models that work in a simulation to what matches reality and this kind of recursive object structure seems to match reality.
So, how does this all factor into your question?  From the CS perspective, a reference frame is just a data model that recursively groups objects to simplify your math.  If I were to take the above class and add a 3rd dimension, energy transfer equations, and all the other weird stuff that makes up real world physics, you would continue to see the same basic principles at work with one notable difference: Relativity basically says that you do not need a top level object, but that you can take any object and re-arrange everything to make that object work like the a top level object.
thing group = (0,0,10,0)
group.thing object1 = (0,0,0,0);
group.thing object2 = (5,0,0,0);
gives the same output as
thing group = (0,0,0,0);
group.thing object1 = (0,0,10,0);
group.thing object2 = (5,0,10,0);
or as
thing group = (5,0,0,0);
group.thing object1 = (-5,0,10,0);
group.thing object2 = (0,0,10,0);
So, this means to do any physics at all, you don't need to understand the top level frame of the universe (if there is one), you can just make all frames relative to any object of interest you want, and it works because every object follows the same functions no matter how you partition it. There are certain forces that are so darn small inside of what we would consider a reference frame that it looks like they don't apply, but even a slug moving along a leaf experiences time dilation; even a feather drifting in the breeze in pulling the Earth with its gravity.