I have an answer here describing the general concept of true physical vectors and tensors which might be useful. (It also might be things you already know very well.)
This turned out to be superlong, I hope you don't die of age before finishing reading. I at least added some useful titles of sections so you can skip some parts. The conclusion is that it is way more plausible for force to be a covector (it's components covariant).
Co(ntra)variant vector or components?
So, we need equations of mathematical physics to be true, which means they are, indeed, invariant. We achieve this by postulating objects such as $\vec{v}$ or $\vec{a}$. We then have equations of this type:
$$\vec{F} = m \vec{a} $$
These are expressible in words and talk about objects which are "real" and thus a notion of them varying with a description is truly absurd. But how do we gain quantitative hypotheses to test from them? We postulate they have certain relations with other objects allowing us to obtain a certain set of numbers completely characterizing such an object. This set of numbers are the components and can be summarized by a following relation (Einstein summation convention included):
$$\vec{v} = v^{\,i} \vec{e}_i$$
That is, the components just give the coefficients of a sum of objects of the same type. We do not get past the veil of this mysterious arrowed object. Ever. Concepts such as direction or velocity cannot be reduced completely to components and there is always this "core" of physics. Vectors are vectors and nothing less. We can however choose a different set of core objects $\vec{e}'_j$. Since $\vec{v}$ is truly invariant, we have
$$v'^j \vec{e}'_j = \vec{v} = v^i \vec{e}_i$$
From arguments sketched in the answer linked in the top of this post, we can deduce the coefficients of the relation $\vec{e}_i = (e_i)^j \vec{e}'_j$. Nonetheless, when we apply it to the previous equation we get
$$v'^j = (e_i)^j v^i$$
$$\vec{e}_i = (e_i)^j \vec{e}'_j$$
Where I put the "core" relation a second time to understand the fact that the components of the vector transform exactly opposite to the basis components. This is also the meaning of the word "contravariance" of the vector components. They transform to counter the variance of the basis, so as a whole the vector will stay invariant. (When any set of object transforms the same as the basis, they co-vary, so they are covariant.)
Note that Fleisch is just stating the just described. The object is invariant, the components transform. He is not saying you can get both covariant or contravariant, you get only one. (You can then use a trick with the metric to change the nature, but the resulting object isn't "the original one". This also addresses your edit concerning relativity.)
A note on the "displacement vector"
The "displacement vector" has it's components only coincidentally transforming as that of a vector in the case of Cartesian coordinates (and flat space) and only when the displacement is taken from the origin. Try moving the origin or switching to polar coordinates or any other curvilinear coordinate system. It's components will transform very differently from e.g. that of velocity.
It is good to remember that for a "true vector" in the sense of component transforms there always has to be something more "differential" about it rather than "difference".
So are the components of force contravariant or what?
As stated e.g. in the answer linked at the top of this post, the ultimate reference "contravariant" vector is the velocity and it's second derivative brother acceleration. In classical physics we definitely want the already mentioned equation $\vec{F} = m \vec{a} $ to hold.
Thus, it would seem straightforward to say that $\vec{F}$ must be a vector with contravariant components because the equation must be invariant (contravariant in components) and the right hand side is a vector. But is it?
There are two conventions. The first one says $m$ is just a number, so $\vec{F}$ must be a vector. But you can see in the answer of Zach McDargh and other comments that it can be a quite neat convention to actually have the force to be a covector. Otherwise, as you correctly observe, we would have to use the already mentioned trick with the metric to raise the indices of the gradient determining the force and other unnecessary junk. I am going to give a quick argument of further elegance elucidating the Newton's law with the so-called mass matrix.
The mass matrix
Consider the kinetic energy, it looks like this
$$T = \frac{1}{2} m v^2$$
But the $v^2$ actually means $\vec{v}\cdot\vec{v}$. However, when we construct classical mechanics and pass to Lagrangian and Hamiltonian mechanics, we find out kinetic energy is the only place where the dot product necessarily enters the construction. We do not need it anywhere else, and everywhere it is, there is also $m$ and vice-versa.
The other funny thing is that with multiple variously constrained particles and with different masses it is practical to describe them all with a single set of coordinates $\mathbf{q} =(q_1,\dots q_N)$. Instead of writing out every kinetic energy term, it is practical to express the whole sum by
$$T = \sum T_{\dots} = \frac{1}{2} \dot{\mathbf{q}}^T \mathbf{M} \dot{\mathbf{q}}$$
with $\mathbf{M}$ the "mass matrix" which is a mix of the metrics of the different particles times their masses, the $1/2$ is conventional, and the dot above the positions means the time derivative.
So even if we stick with just one particle, it seems natural to define the "mass matrix" as $M_{ij} = m g_{ij}$ with $g_{ij}$ the metric ($\delta_{ij}$ for the dot product in Cartesian coordinates in flat space). If we insist on the fact that the metric or mass never occur in dynamical equations separately, we reduce one element of our theory without changing it's physics. Occam's razor! It's simpler so it has to be done! (Until we want to measure angles and distances in a non-dynamical context...)
So, the mass matrix has two lower indices and is doubly covariant, the same as the metric. If we then contract it with a vector in one index we get e.g.
$$p_i = M_{ij} v^j$$
Momentum is thus a covector whose components transform covariantly. It is now obvious that we have
$$\vec{F}=m\vec{a} \to F_j = M_{ij} a^i$$
Or even better for systems with varying mass
$$F_j = \frac{d}{dt}p_j$$
So there is no problem with Newton's equation and it's covariance. By this argument, it is much more natural to define force to be a covector.
A feinschmecker note: You might argue that the concept of a mass matrix is not needed for the whole argument. But I am assuming we are not Landau, and we want to find an elegant form of the Newton's law without an arbitrarily placed metric instead of "deriving" the Newton's law from Lagrangian mechanics.