First, to clarify, the first Lagrangian you gave is the Lagrangian describing a non-relativistic point particle moving in a fixed background potential $(\phi,\textbf{A})$. The second Lagrangian describes the dynamics of the electromagnetic field in the presence of a fixed background source $(\rho,\textbf{j})$.
Now, the short answer to why the minus sign is there is that, without it, the equations obtained aren't Maxwell's equations.
A slightly longer answer is that the minus sign exists to ensure relativistic invariance. Under a Lorentz transformation, the electromagnetic fields transform as
$$\textbf{E}_{\perp}\to\gamma\left(\textbf{E}_{\perp}+\textbf{v}\times\textbf{B}\right),\hspace{0.5cm}\textbf{B}_{\perp}\to\gamma\left(\textbf{B}_{\perp}-\frac{1}{c^2}\textbf{v}\times\textbf{E}\right),$$
where $\perp$ denotes the component of the field perpendicular to boost velocity $\textbf{v}$. Under this transformation, we have
$$\frac{\epsilon_0}{2}\textbf{E}^2-\frac{1}{2\mu_0}\textbf{B}^2=\left(\frac{\epsilon_0}{2}E_{\parallel}^2-\frac{1}{2\mu_0}B_{\parallel}^2\right)+\frac{\gamma^2\epsilon_0}{2}\left(\textbf{E}_{\perp}+\textbf{v}\times\textbf{B}\right)^2-\frac{\gamma}{2\mu_0}\left(\textbf{B}_{\perp}-\frac{1}{c^2}\textbf{v}\times\textbf{E}\right)^2.$$
Being careful with our cross product identities, we can show
$$(\textbf{E}_{\perp}+\textbf{v}\times\textbf{B})^2=\textbf{E}_{\perp}^2+\textbf{v}^2\textbf{B}^2-\left(\textbf{v}\cdot\textbf{B}\right)^2+2\textbf{E}\cdot\left(\textbf{v}\times\textbf{B}\right)$$
$$\left(\textbf{B}_{\perp}-\frac{1}{c^2}\textbf{v}\times\textbf{E}\right)=\textbf{B}_{\perp}^2+\frac{1}{c^4}\textbf{v}^2\textbf{E}^2-\frac{1}{c^4}\left(\textbf{v}\cdot\textbf{E}\right)^2-\frac{2}{c^2}\textbf{B}\cdot\left(\textbf{v}\times\textbf{E}\right).$$
Plugging this directly into the transformation of the Lagrangian shows that the $\gamma$ factors cancel, and the Lagrangian is relativistically invariant.
The longest answer requires the language of differential forms to truly appreciate. If $A$ is the electromagnetic 1-form, and $F=\mathrm{d}A$ is its corresponding field strength, the canonical action for this $U(1)$ gauge theory is given by
$$S=-\frac{1}{2}\int_{\mathcal{M}} F\wedge\star F.$$
Now, to express this in terms of the electric and magnetic field, we note that if we have an orthonormal basis $\{\mathrm{d}x^\mu\}$ of $\Omega^{1}(\mathcal{M})$ (the space of one-forms on $\mathcal{M}$), we can define an electric field one form
$$E=E_{1}\mathrm{d}x^1+E_{2}\mathrm{d}x^2+E_{3}\mathrm{d}x^3.$$
Next, we can define a magnetic field 2-form
$$B=B_1\mathrm{d}x^2\wedge\mathrm{d}x^{3}+B_2\mathrm{d}x^3\wedge\mathrm{d}x^1+B_3\mathrm{d}x^1\wedge\mathrm{d}x^2.$$
In terms of these variables, the field strength is decomposed as
$$F=B+E\wedge\mathrm{d}x^0.$$
Now, when evaluating $F\wedge\star F$, the hodge star of $E\wedge\mathrm{d}x^0$ will have an extra minus sign relative to the $B$ term, coming from the minus sign in the metric tensor $g=\text{diag}(-1,1,1,1)$. This is the mathematical origin of the minus sign.
In summary, there are three answers to this question, with three different levels of intuitive satisfaction:
- The minus sign is there to ensure that the equations of motion obtained are Maxwell's equations (not that satisfying).
- The minus sign is there to ensure relativistic invariance of the action (somewhat satisfying).
- The minus sign comes from the minus sign in the Minkowski space metric tensor (very satisfying).