Generalized Forces and Potential Energy Consider a (conservative) system of $N$ particles with $\vec{r}_i$ being their positions.
In this system, there are attractive and repulsive forces between these particles. $\vec{F}_i$ shall be the net force acting on particle $i$ in some configuration of the system.

For now, let's consider the particles are not subject to any constraints, i.e. they could possibly be found at an $\vec{r}_i \in \mathbb{R}^2$. My intuition is that displacing a particle an infinitesimal distance in the direction the net force $\vec{F}_i$ is acting in, i.e. 'giving in' to the force, would reduce the system's potential energy, due to the way physical work is defined:
$$ W = \int F(s) \enspace ds $$
Is my intuition correct? How can I go about formally proving this?

Let us now consider the system is subject to some constraints. We can use generalized coordinates $\vec{q} = (q_1, \ldots, q_n)$ to describe the system's configuration, implicitly satisfying all constraints.
I read about generalized forces which are defined as
$$ Q_j = \sum\limits_{i=1}^{N}{\vec{F}_i \cdot \frac{\partial \vec{r}_i}{\partial q_j}}, \qquad j = 1, \ldots, n. $$
My intuition here would be that adjusting a generalized coordinate $q_i$ by an infinitesimal amount in direction $Q_i$ would again reduce the system's potential energy. Is this intuition still correct? How do the constraining forces play into this? Do I have to include those in $\vec{F}_i$? Again, how could I prove this intuition?
 A: Up-front comments that will make things seem obvious

Consider a (conservative) system of $N$ particles with $\vec r_i$ being their positions.

Oh, good. So there is presumably some potential energy function $U(\vec r_1,~\vec r_2,~\dots,\vec r_N).$

In this system, there are attractive and repulsive forces between these particles. $\vec F_i$ shall be the net force acting on particle $i$ in some configuration of the system.

All right, so we technically need some $\nabla_i = \left(\frac{\partial}{\partial x_i},~ \frac{\partial}{\partial y_i},~\frac{\partial}{\partial z_i}\right)$ operators and then $\vec F_i = -\nabla_i U.$ No problem.
It sounds like you might not be so familiar with partial derivatives; the basic story is that in $D$-dimensional space $\mathbb R^D$ we approximate a function from $\mathbb R^{D-1} \to \mathbb R,$ which carves out some $D-1$-dimensional "hypersurface," by $D-1$-dimensional "hyperplanes" which are flat and tangent to the surface. In other words this function $x_D = f(x_1, x_2, \dots x_{D-1})$ is held to be approximately equal to the plane $x_D = c_0 + c_1~x_1 + c_2~x_2 + \dots + c_{D-1}~x_{D-1}$ in a small neighborhood about some point. These terms $c_i$ are "the partial derivative of $f$ with respect to its $i^\text{th}$ argument holding the other arguments constant," which is the Mathematically True way of looking at partial derivatives, though the other way (that you were likely taught first to think of them) is not too far off from it.1 Of course we can repeat this process at each point, getting a new tangent plane, so these are really $c_i(x_1,\dots,x_{D-1}).$ We can equivalently get surface normal vectors to these surfaces by going one dimension higher and defining  $g(x_1\dots x_D) = f(x_1\dots x_{D-1}) - x_D$ and taking the $D$-dimensional gradient $\nabla g = [c_1,\dots c_{D-1}, -1],$ if you prefer to think of it that way.2
Question 1: work reduces potential energy.

My intuition is that displacing a particle an infinitesimal distance in the direction the net force $\vec F_i$ ... would reduce the system's potential energy... Is my intuition correct? How can I go about formally proving this?

Yes, your intuition is correct. The new potential energy after moving particle $i$ by an amount $\delta \vec r_i$ is $$U + \delta_i U = U(\vec r_1,~\dots\vec r_{i-1},~\vec r_i + \delta \vec r_i,~\vec r_{i+1},~ \dots \vec r_N).$$ The approximation with the tangent plane says $$\delta_i U = U(\dots~,x_i + \delta x_i, y_i + \delta y_i, z_i + \delta z_i,~\dots) - U \approx \frac{\partial U}{\partial x_i} ~\delta x_i + \frac{\partial U}{\partial y_i} ~\delta y_i + \frac{\partial U}{\partial z_i} ~\delta z_i,$$ or with a little more conciseness and generality we would say instead that for any infinitesimal displacement of the particles of the system $\delta\mathbf{r} = \{\delta\vec r_i\}$ we change the potential energy by $$\delta U = \mathbf{\nabla} U\cdot \delta \mathbf{r} = \sum_i \nabla_i U\cdot\delta \vec r_i.$$I hope that's clear enough, $\nabla$ being the full $3N$-dimensional gradient $$\nabla = \left(\frac{\partial}{\partial x_1},~ \frac{\partial}{\partial y_1},~\frac{\partial}{\partial z_1},~\frac{\partial}{\partial x_2},~\dots\right)$$ and $\mathbf r = (x_1, y_1, z_1, x_2, \dots)$ being the full $3N$-dimensional position. I will use these again in a moment.
Anyway by the definition of the potential energy as the function which solves these differential equations, $\vec F_i = -\nabla_i U,$ it is clear that $\delta U = \sum_i \nabla_i U\cdot\delta \vec r_i = -\sum_i \vec F_i \cdot \delta\vec r_i,$ which is exactly what you asked to prove. If you hold $N-1$ of them fixed $\delta\vec r_i = 0$ and only vary one of them $\delta \vec r_k \ne 0$ you change the potential energy by $\delta U = -\nabla_k U \cdot \delta \vec r_k.$
Question 2: same question with generalized forces

My intuition here would be that adjusting a generalized coordinate $q_i$ by an infinitesimal amount in direction $Q_i$ would again reduce the system's potential energy. Is this intuition still correct? 

I mean the easiest way to do this (and any work with constraint forces) is to work with the Lagrangian of the system in which case you can struggle to define "potential energy" with the easiest definition yielding a violation of your intuition.3 However your definition of "generalized force" and the Lagrangian's definition of "generalized force" are not equivalent.
With your definition it seems straightforward to say,$$\sum_k U_k ~ \delta q_k = \sum_{ik} \vec F_i \cdot \frac{\partial \vec r_i}{\partial q_k} ~\delta q_k = \sum_{i} \vec F_i \cdot \delta \vec r_i = -\delta U,$$ as above. The Lagrangian formalism appears to include what might be called "inertial forces" in its generalized force, whereas your definition does not. All you really require is the statement $\sum_k \frac {\partial \vec r_i}{\partial q_k} ~\delta q_k = \delta \vec r_i,$ but just look at its $x, y, z$ components and you'll see the exact same story that we've repeated a couple of times now, that if you have $x_i(q_1, q_2, \dots)$ then $\delta x_i = \frac{\partial x_i}{\partial q_1} ~ \delta q_1 + \frac{\partial x_i}{\partial q_2} ~ \delta q_2 + \dots,$ and the above equation holds as a trivial generalization.
So again, there is a definition of "generalized force" which will not obey your intuition, though there may be a definition of "generalized potential energy" which will then help you out again... but your definition is not it, and will always obey your intuition. (If you didn't read the footnote, the other definition says "here are my generalized momentums $p_i$, my generalized forces are $dp_i/dt.$" That's why you get inertial forces in there if your coordinates allow for them.)
Question 3: constraint forces

How do the constraining forces play into this? Do I have to include those in $\vec F_i$? Again, how could I prove this intuition?

Well, what's the simplest thing that works? Say you have some constraint $f(\vec r_1, \vec r_2, \dots \vec r_N) = C.$ We can model this by adding to $U$ some term $\alpha [f(\dots) - C]^2$ for some very large $\alpha,$ this will make the energy cost to leave the constraint become extremely high. 
The resulting generalized force therefore also has this very huge term, $Q_k' = Q_k + 2\alpha ~f~\nabla f\cdot\frac{\partial \mathbf r}{\partial q_i}.$ (Told you I'd use it again!) Or does it? What does it mean for a motion to obey the constraints? It really means that $\delta f = \nabla f\cdot\delta\mathbf{r}$ must be $0$ to preserve $f(\dots) = C.$ So if all of these $q_i$ obey the constraint individually, then each $\partial\mathbf r/\partial q_i$ must be perpendicular to $\nabla f$ to force $\delta f = 0.$ Sp actually $Q_k' = Q_k.$ Even though we are worried because $\alpha$ is huge, we can relax precisely because our coordinates embody, never violate, the constraints.
Question 4: the minimum energy principle

[in a comment] "Exactly the the same way that you would prove why a compressed or extended spring would go to its equilibrium position." – it makes perfect sense to me; but I still have no clue on how I could formally prove that.

This is actually somewhat difficult to prove in a conservative system, as it should be, because the energy is conserved and the compressed spring should not be returning easily to its equilibrium position but rather oscillating around it!  The easiest way is to notice that drag forces typically oppose velocity and therefore do negative work, leading to an expectation of total energy minimization: the kinetic energy gets minimized at $v_i = 0$, the potential energy gets minimized wherever.
To keep the system conservative the biggest mechanism is to couple it weakly to an infinite number of other degrees of freedom, for example oscillators, and then to derive the equations of motion and take limits and approximations which ignore more and more of the other degrees of freedom and the energies in them. You find a similar flow of energy "out" of "the part of the system we care about" and into "the part we don't care about." Then you realize that there should also be a flow back in when the energy gets low enough: et voilà, you have rediscovered thermal fluctuations.
Some Footnotes


*

*You were probably instead taught to take a derivative with respect to a symbolic expression $p(x_1, \dots x_n)$ while holding $D-2$ other symbolic expressions $q_i(x_1, \dots x_n)$ constant, where often the symbolic expressions are very trivial like $p = x_1$ but sometimes they are complicated like $r = \sqrt{x_1^2 + x_2^2 + x_3^2}.$ This is not too hard to define, theory-wise. It requires inverting those symbolic expressions to solve them for some functions $x_i(p, q_1, q_2, \dots q_{D-2})$ and then substitute them in, defining $g(p, \vec q) = f(x_1(p,\vec q),~x_2(p, \vec q),~\dots)$. The derivative of $g$ with respect to its first argument is then the definition for "the derivative of $f$ with respect to the symbolic expression $p$ holding the other symbolic expressions for the other $q_i$ constant."

*I just wanted to mention that if you view gradients as normal vectors to level sets $g(\dots) = C$ then you get a nice interpretation of Lagrange multipliers as vector rescalings. "To increase $f$ on $g(\dots) = C$ then you need to take a step in the direction of $\nabla f$, of course you can't make this step exactly but you can step in the direction of the projection normal to $\nabla g$, $\nabla f -(\nabla f\cdot\nabla g)\nabla g/|\nabla g|^2,$ and still increase it. The only way to be at a maximum is if the above step doesn't get us anywhere because it is zero because the two vectors $\nabla f$ and $\nabla g$ are parallel, $\nabla f = \lambda ~ \nabla g$." Boom, $\lambda$ is your Lagrange multiplier.

*The Lagrangian of a conservative system of particles is $L = \sum_i m_i v_i^2 / 2 - U,$ re-expressed in terms of coordinates $\{q_i, \dot q_i\}$ which embody your constraints directly. The Euler-Lagrange equations specify a generalized momentum $p_i = \partial L/\partial \dot q_i$ for each coordinate $q_i$ and a generalized force $F_i \partial L/\partial q_i,$ then tell you that the equations of motion are always $dp_i/dt = F_i,$ and again there is no need to fuss with constraints. With that said, it's not always so obvious how to recover a notion of "potential energy" from the Lagrangian, but the easiest way is to define the Hamiltonian $H = -L + \sum_i ~p_i ~\dot q_i,$ which intuitively is $H = K + U$ to the Lagrangian's $L = K - U$, hence you get $U = (H - L)/2 = -L + \frac12 \sum_i ~p_i ~\dot q_i.$ Now you can see, "it depends." Obviously $F_i ~\delta q_i = \delta_i L$ based on the definition of generalized force, so if this is positive then the leading term is negative and the potential energy "wants" to decrease. However if some $p_k$ depends on $q_i$ and $\dot q_k$ is very large already, it might well increase. An example of this would be a spinning system where the angular momentum works out like $p_\theta = \partial L/\partial {\dot \theta} = mr^2\dot \theta,$ a step to greater $r$ at high values of $\dot theta$ might increase $L$ but increase $p_\theta ~\dot \theta$ more, so that $U$ increases even though $L$ increases too. Basically this is a centrifugal force term pulling the thing against a potential that wants to hold it closer to the center; the generalized force includes the centrifugal force, but the above definition of potential energy does not, so when the centrifugal force is stronger than the potential you see a situation where the generalized force points in a direction that increases the total potential energy, not decreases it.

A: We use the term potential "energy" because it is strongly related to the work. The relation between the potential energy and the work is not something that you can prove, but somewhat we have defined.
If you introduced the potential energy first, you can define the force on a particle as follow:
$$
\vec{F}(\vec{r}) := -\frac{\mathrm{d}U}{\mathrm{d}\vec{r}}(\vec{r})
$$
You can calculate the work from the force above.
OR, if you introduced the force first, you define (difference of) the potential energy as follow:
$$
U(\vec{r}_f) - U(\vec{r}_i) := -\int_{\vec{r}_i}^{\vec{r}_f} \vec{F}(\vec{r}) \cdot \mathrm{d}\vec{r}
$$
note: $U$ must be conservative or the relation would be ill-defined. And you know the condition for the conservative part ;)
By the way, you can increase the potential energy of the system by moving the particle by infinitesimal distance.
A: Because the first sentence of the question is

Consider a (conservative) system of $N$ particles with $\vec{r_{i}}$ their positions.

I assume that in both parts of your question you are talking about a conservative system.
Let me try to answer the first part.
If the system is in equilibrium then the total energy of the system is minimum and the total force in the system is zero. If the system is not in equilibrium and there are no constraints on the particles then the particles will move (adjust themselves) until they minimise the total energy and diminish the force.
You say that

$\vec{F_{i}}$ shall be the net force acting on particle $i$ in some configuration of the system.

which means that this is not an equilibrium configuration and the particles will move until "hopefully" they find the minimum of the potential energy surface and settle there (of course there is a possibility of system being trapped in a local minimum). Therefore I agree with your statement:

My intuition is that displacing a particle an infinitesimal distance in the direction of the net force would reduce the system's potential energy.

And you ask

How can I go about formally proving this?

Exactly the the same way that you would prove why a compressed or extended spring would go to its equilibrium position.
In the second part of your question you talk about the generalised force (please take my answer to second part with a grain of salt).
As far as I know in the Lagrangian formalism (I use this because one of the tags of the question is lagrangian-formalism) the Lagrange equation of motion can be written as
$$\frac{\partial }{\partial t}\left ( \frac{\partial L}{\partial \dot{q_{i}}} \right )-\left ( \frac{\partial L}{\partial q_{i}} \right )=0$$
and this is only true for conservative systems, otherwise the equation reads
$$\frac{\partial }{\partial t}\left ( \frac{\partial L}{\partial \dot{q_{i}}} \right )-\left ( \frac{\partial L}{\partial q_{i}} \right )=Q_{i}$$
That is to say the conservative forces that you talk about in the first part of your question that are attractive and repulsive and keep the system together is not the same kind of forces that you talk about in the second part.
In any case, if there is non-conservative (that is not derivable from a potential) forces in your system to calculate the particle trajectories you need to solve the second Lagrange equations of motion given above.     
A: The generalized coordinates will (well... should) already contain the constraints.  For instance, in the case of a pendulum of length $\ell$ the generalized coordinate is usually the arclength $\ell\theta$ or the angle $\theta$ itself, rather than the Cartesian coordinates $x$ and $y$ (vertical is $y$).  
The constraint $x^2+y^2=\ell^2$ precisely allows the passage from Cartesian to generalized coordinates.  Thus, the forces of constraint have been "eliminated" by going to generalized coordinates.  In the simplest cases, the $\vec F_i$ should be the Cartesian components (or at least the components in the original coordinates).  The parts of $\vec F_i$ that contribute no net work (such as action-reaction pairs) will be automatically be eliminated by the summation over all particles.
If you want to get more formal, there is a old textbook by Whittaker with lots of details.  Otherwise, Goldstein is the usual standby but also there are lots of engineering text dealing with the method of virtual work that would be useful at various levels of formality.
