According to relativity (both Galilean and Special) no reference frame is fixed.
This is correct. However, they do single out a set of frames, the so called inertial frames. These are the frames, in Galilean relativity, where objects with no net force on them travel at uniform speed in a straight line or remain at rest (this is just a specialisation of the former for zero speed).
but if that were the case, why do we feel fictitious forces when being in a car that's accelerating with respect to a road
This is because an accelerating frame is not an inertial frame. The frame, to accelerate, must feel a force and then for the car frame, this force is transmitted to your body. And so you feel a 'fictitious force'. However, in this case the force is real.
Instead, consider a ball freely moving in space. Thus it is moving in a straight line at constant speed. Then suppose you shoot by in an accelerating rocket. Then the ball, from the rocket frame looks as though it is accelerating. Thus it, by Newton's second law, looks as though a force is applied to the ball to make it accelerate. This is a fictitious force.