Can we describe the classical laws of physics in a frame-of-reference-independent way? First of all, I am not a physicist, so I cannot guarantee things I say will make sense. I will try my best, though.
In classical mechanics we have the notion of inertial frame of reference. If my understanding is correct, such frames are exactly those for which Newton's laws of motion have the usual form. I believe I have also heard, that they are the frames that are "moving at a constant speed" with respect to some distinguished point in space.
So we have to be careful whether our frame is accelerated or not. Which makes me wonder:

Does there exist a set of physical laws (of same descriptive power Newton's laws have, but perhaps expressing relations in some other set of physical quantities) such that the laws from this set look the same, no matter how the frame of reference moves?
Does such a set of physical laws exist if we restrict to polynomially moving frames of reference? (By this I mean that the motion of the frame is described by a polynomial in $t$, where $t$ is time.)

I imagine this could simplify some calculations.
 A: Relativity achieves just what you describe, and does it for all physical laws, in all frames of reference, accelerated or not, and not even restricted as per your 'polynomial' stipulation.  
To even make this work in uniform-motion frames, Special Relativity had to add a little complexity to Newton's equations, which otherwise would break down if the speeds involved in that uniform motion are very high.
Even more complexity was needed to encompass all reference frames, regardless of acceleration, or influence of gravity.  But the resulting laws and equations are universally valid. (perhaps not at the quantum/particle level, however).
I'm not sure this bit: 'with respect to some distinguished point in space' is accurate WRT what Newton said, but regardless, it is not necessary after Relativity.
A: You can indeed!!!! Relativity is not a good answer since you are asking for classical (Newtonian) Mechanics. There are two approaches. The first one is that of differential geometry. In it you realize that the problem of evaluating Newton's equations in non-inertial frames is that acceleration introduces curvature to the coordinates systems used. This is expressed with a mathematical symbol called the cristoffel tensor. I suggest you follow Schaum's Tensor Calculus or Grinfeld's Tensor Analysis and the Calculus of Moving Surfaces for more on this. In that case you arrive to the equation $$F^i=m\frac{\delta v^i}{\delta t}$$Another approach is that of analytical mechanics. In it you restrict yourself to a certain kind of systems (monogenic, holonomic, etc....) which lets you formulate mechanics in terms of what is called generalized coordinates. The formula you get is $$\frac{\textrm{d}}{\textrm{d}t}\frac{\partial \mathcal{L}}{\partial \dot{q}^i}-\frac{\partial \mathcal{L}}{q^i}=0$$
