Part 1
Monotonicity under channels is sometimes also referred to as satisfying a data-processing inequality. One way to prove this is to use a variational formula for the fidelity function, see Theorem 3.17 and the subsequent discussions in TQI - Watrous. This is slightly cheating as you first need to prove the variational formula is correct but in my experience data-processing follows quite quickly once you have a variational formula. So the fidelity can be rewritten as the semidefinite programming problem
\begin{equation}
\begin{aligned}
F(\rho, \sigma) = \,&\max_{X} \quad\mathrm{Tr}[X + X^*]/2 \\
&\,\,\mathrm{s.t.} \quad \begin{pmatrix} \rho & X \\ X^* & \sigma \end{pmatrix}\geq 0
\end{aligned}
\end{equation}
where the maximization is over all linear operators $X$ on the Hibert space which $\rho$ and $\sigma$ act on.
Now take any quantum channel $\mathcal{N}$ and take any feasible point $X$ for the SDP characterization of $F(\rho, \sigma)$. As $\mathcal{N}$ is a completely positive map we have
$$
\begin{pmatrix} \rho & X \\ X^* & \sigma \end{pmatrix}\geq 0 \implies \begin{pmatrix} \mathcal{N}(\rho) & \mathcal{N}(X) \\ \mathcal{N}(X)^* & \mathcal{N}(\sigma) \end{pmatrix}\geq 0.
$$
Furthermore we have $\mathrm{Tr}[X + X^*]/2 = \mathrm{Tr}[\mathcal{N}(X) + \mathcal{N}(X)^*]/2$ as $\mathcal{N}$ is trace-preserving. Thus we have shown that for each feasible point $X$ of the SDP for $F(\rho, \sigma)$ we can define a feasible point $\mathcal{N}(X)$ of the SDP for $F(\mathcal{N}(\rho), \mathcal{N}(\sigma))$ which has the same objective value. As we are taking a maximization over all feasible points it follows that we must have $F(\rho, \sigma) \leq F(\mathcal{N}(\rho), \mathcal{N}(\sigma))$.
Part 2
First note that it is the same channel that is being applied to the two states $\rho$ and $\sigma$. So if for example $\rho = \sigma$ and they have perfect fidelity then $\mathcal{N}(\rho) = \mathcal{N}(\sigma)$ and the `noisy' outputs also have perfect fidelity. On the opposite end of the spectrum if we take a channel which produces white noise i.e., $\mathcal{N}(\rho) = \mathrm{Tr}[\rho] I/d$ then $\mathcal{N}(\rho) = \mathcal{N}(\sigma)$ for any two states $\rho$ and $\sigma$. Thus even those that previously had fidelity $0$ will have, after sending them through this maximally noisy channel, perfect fidelity.
A better way to think of this result is to think of the fidelity as a measure of how well we can distinguish two quantum states (where values closer to $0$ are more distinguishable). This interpretation is justified by the Fuchs-van de Graaf inequalities that relate the fidelity and the trace distance and the trace distance's operational characterization as a distinguishability measure that comes from Holevo-Helstrom theorem. Taking a step back, if we were to have any hope that the fidelity is a good measure of distinguishability then it would have to be the case that the fidelity satisfies a data processing inequality. For if we are to think that $F(\rho, \sigma)$ really characterizes our ability to distinguish $\rho$ from $\sigma$ then it shouldn't be the case that we can send the unknown states through some quantum channel and then distinguish them better, i.e. $F(\rho, \sigma) \not\geq F(\mathcal{N}(\rho), \mathcal{N}(\sigma))$.
