A concise definition of a frame of reference in Newtonian mechanics?

A frame in Newtonian mechanics is exactly the same thing as it is in relativity: An ordered orthonormal set of four vectors (or fewer if your mechanics are confined to, say, a plane or a line), the first of which is timelike and future-directed. In Newtonian spacetime, unlike in relativity, there is (at any given event) exactly one timelike and future-oriented direction, which uniquely determines the first vector. The other three can be any orthonormal basis for ${mathbb R}^3$.

In first year physics, a chosen coordinate system defines the frame of reference, and as Safesphere points out, it is chosen relative to some object (like the earth).

In my understanding a frame of reference is a structure that quantifies the term "at rest". To go into detail we first have to clearify the framework we are in, i.e. the spacetime structure. For Newtonian mechanics this would be the Galileian spacetime. In beginner courses this is often introduced as $M=mathbb{R}timesmathbb{R}^d$, a Cartesian product of a time dimension and $d$-dimensinal space. However, this construction posseses a special point, the zero vector, as well as distinguished directions, the standard vectors of $mathbb{R}^4$. This is why we take a more ambitious path and define the spacetime on an affine space. This is a set $M$ togehter with a free and transitive action $+:Mtimes Vrightarrow M$ of a vectorspace $V$. This essentially means that $M$ is a space allowing translations as a vector space and "looking like" a vectorspace, but without a distinguished zero point or special directions. To talk about spacetime, we also need a linear map $t:Vrightarrow mathbb{R}$, call it time map. Given two points $m_1,m_2in M$, there is exactly one vector $vin V$ such that $m_2=m_1+v$ (follows form free and transitive). The mapping $t$ then maps this vector $v$ to the time difference between spacetime point $m_1$ and $m_2$. Note, that $t$ gives us a notion of time without setting a distinguished time direction. This manifests that there is no distinguished time direction in Galileian spacetime. We call a vector $vin V$ future directed if $t(v)>0$ and instantaneous or spacelike if $t(v)=0$. If $M$ is $d+1$ dimensional, the time map induces a foliation of $M$ in $d$ dimensional instantaneous subspaces. These are "space".

We now have the right framework to talk about frames of reference and coordinate systems. So let's start with coordinate systems. They do not have anything to do with "time directions" or frames of reference at the the first place. The interpretation of one coordinate as "time coordinate" is only possible in combination with a frame of reference. However, nothing forces us to choose coordinates with such an interpretation, take for example lightcone coordinates $(u,v)=(x+ct,x-ct)$ in Minkowski spacetime. Coordinates just put a lable to each point of $M$, they do not even have to "know" about time existing.

On the other hand, a frame of reference gives a notion in which direction time "flows". Or seen from another perspective, it defines a notion for the term "at rest", which has precisely nothing to do with a coordinate system. But enouth talking, techinically a frame of reference is a (smooth) vectorfield on $M$, i.e. a map $f:Mrightarrow V$, with the property that $tcirc f = 1$. In words, this is a time-normalized vector at each point $min M$ pointing in the direction that is "at rest", i.e. a particle at $min M$ moving in direction $f(m)$ is at rest with respect to the frame $f$. If $gamma:mathbb{R}rightarrow M$ discribes a particle moving through spacetime (has to satisfy $t(dotgamma(t))>0$ to be future directed) we now can define its velocity with respect to the frame f by $$v_gamma^f(t):= frac{dotgamma(t)}{t(dotgamma(t))} - f(gamma(t)).$$ It may looks complicated, but it is just the difference of the time normalized direction the particle is moving and the direction that would be "at rest". Note that this velocity is instantaneous. I might add that an inertial frame is a frame of reference invariant under the translation action, i.e. $f(m+v)=f(m)$ for all $vin V$.

Ok, now that we defined both, frames and coordinates, let's get to the question how they work together. Having choosen a frame $f$, we can introduce coordinates respecting $f$ in the sense that one coordinate line always run in direction of $f$ and the others lie in the instantaneous subspace. More technically, a coordinate system induces a basis in the tangent space of $M$ at each point, which can be identified with $V$. A coordinate system respects $f$ if, at each point $pin M$, the first coordinate tangent vector equals $f(p)$ and the others are instantaneous, i.e. $t$ maps them to zero. The confusion between coordinate system and frame of reference typically arises because we choose a coordinate system such that the tangent vector of the first coordinate defines a vector field that is a frame of reference. However, this is not true for all coordinate systems and we do not have to work in coordnates compatible with a frame of reference.

As a conclusion, a coordinate system and a frame of reference are fundamental different structures on a spacetime. The first lables each spacetime point so that we can work with spacetime on paper, the latter defines what "at rest" means for a particle. However, they are mostly used compatible so that they do not have to be seperated that strictly. One can extend this discussion to other spacetimes, for example concerning general relativity. Furthermore, this stuff can be treaten way more mathematically sophisticated, check for example the answer of Ittiolo in this related question.