As you noted, the key issue is that Newton's Third Law is a statement about forces on two different objects:
$$
\vec{F}_\text{A on B} = - \vec{F}_\text{B on A}
$$
Therefore you will never see these two forces within the same free-body diagram; they cannot "cancel out".
Draw the free-body diagram for the horse. There are: a tension force of the carriage backwards on the horse; a force of gravity downward on the horse; a normal force of the ground upward on the horse; and a static frictional force of the ground on the horse, pointing forward. If we state these forces with explicit reference to "object acting on object", they are:
$$
\vec{F}_{T, \text{ carriage on horse}}\,, \, \,
\vec{F}_{g, \text{ earth on horse}}\,, \, \,
\vec{F}_{N, \text{ ground on horse}}\,, \, \,
\vec{F}_{fs, \text{ ground on horse}}
$$
Note that all of these forces belong on the free-body diagram of the horse, and are all "on horse". The acceleration of the horse will be determined, through Newton's Second Law, by the vector sum of these forces. In particular, for the horse to accelerate forward, the fourth of these forces must be larger in magnitude than the first. Those two forces are in no way related by Newton's Third Law.
The Newton's Third Law pairs of each of those forces are easy to write down (just reverse the "object on object", but maintain the type of force):
$$
\vec{F}_{T, \text{ horse on carriage}}\,, \, \,
\vec{F}_{g, \text{ horse on earth}}\,, \, \,
\vec{F}_{N, \text{ horse on ground}}\,, \, \,
\vec{F}_{fs, \text{ horse on ground}}
$$
The first two forces belong in the free-body diagrams of the carriage and the (whole) earth, respectively, while the last two are on the free-body diagram of the ground. The acceleration of each of those objects will be due to the sum of forces in their own free-body diagrams. Again, Newton's Third Law plays no role in their dynamics.
The necessity of Newton's Third Law is to extend the dynamics of a single particle (which is prescribed by Newton's Second Law) to the dynamics of systems of particles. From this simple connection you can build up a theory the predicts the dynamics of rigid objects, clouds of particles interacting, fluids, and galaxies of stars.