First of all, we are fundamentally interested in E & B. But essentially, it comes down to the fact that only E and B are physically measurable and so $\phi$ and A are mainly only considered as mathematical constructs, but this isn't always true - they can be conceptualised.
I apologise that I cannot give you an immediate physical insight, but I can only first explain via the math and then show what it means.
By the helmholtz theorem, which is really a mathematical construct rather than a physical insight, shows that we can rewrite E & B as a combination of a vector potential & scalar potential.
The theorem reads that any vector field (which E & B are) can be written as:
$$\mathbf{ F} = - \boldsymbol{\nabla} \phi +\boldsymbol{\nabla} \times \mathbf{A} $$
So we can rewrite E and B as
$$\mathbf{ E} = - \boldsymbol{\nabla} \phi +\boldsymbol{\nabla} \times \mathbf{A} $$
$$\mathbf{ B} = - \boldsymbol{\nabla} \phi +\boldsymbol{\nabla} \times \mathbf{A} $$
But we know that in electrostatic situations the curl of the E field is zero. In this case the electric field is conservative and only determined by the gradient of the potential. So,
$$\mathbf{ E} = - \boldsymbol{\nabla} \phi $$
The fact that B =$\boldsymbol{\nabla} \times \mathbf{A} $ is a little bit more involved. We know that no magnetic monopoles exist so there can be no sinks or sources so
$$ \boldsymbol{\nabla} \cdot \mathbf{B} = 0 $$
There is also a second part of the Helmoltz theorem which gives that
$$\phi(\mathbf{r})=\frac{1}{4\pi}\int\int\int\frac{\boldsymbol{\nabla}\cdot\mathbf{B}}{|\mathbf{r-r'}|}\textrm{d}V'$$
and
$$\mathbf{A}(\mathbf{r})=\frac{1}{4\pi}\int\int\int\frac{\boldsymbol{\nabla}\times\mathbf{B}}{|\mathbf{r-r'}|}\textrm{d}V' $$
We can now see that $\phi(\mathbf{r})$ must be zero. Which means that
$$\mathbf{ B} = \boldsymbol{\nabla} \times \mathbf{A} $$
By working with $\phi$ and A it can greatly make our mathematical constructs simpler and make it easy for us to calculate the E and B fields. I can't convince you of this immediately, but hopefully you can see how the above expressions look simpler than the Biot Savart law, for instance.
The minus sign in our expression for E reflects the fact that positive charges move from high potential to low potential, so in the direction opposite the steepest increase in the potential function. This is purely conventional. Further we now that the E field is conservative. You can take any route from a to b and the value of the below integral is the same:
$$\phi(\mathbf{r})=-\int_O^r \mathbf{E}\cdot \textrm{d}\mathbf{l}$$
with O as the place where we say potential is taken to be 0. This might arise to some confusion as we don't define a route, but, because the E field is conservative, it won't matter. We can place the zero point whereever we want - we can even add a constant, because we are only interested in the derivative because the E field is the only thing physically measurable.
In most electrostatic situations it will be easier to calculate the electric potential than the E field directly. Note, if we do have moving charge, we'll have a B field from Maxwell-Amperes law. This means that the curl of the E field is no longer zero.
Do not confuse electric potential with potential energy. The electric potential has one particular value at each point in space, independent of whatever charge you might place there, and its gradient gives you the electric field (which is the force per unit charge, also independent of the actual amount of charge placed at that point). To determine the potential energy (derivation not given) U=q$\phi$
So, now to your physical interpretation for A. We know we can have a physical interpretation for the scalar potential, but is A anything special?
For most purposes it's fine to think of the vector potential as a convenient mathematical tool without any physical meaning, but it does have a physical interpretation. By inspection, we can see that A has units of momentum per charge, and we can think of A as the "momentum per unit charge" that's stored in the electromagnetic field. This is analogous to potential energy, but its a potential momentum.
Further, The vector potential is an important quantity in many areas of modern physics (superconductivity, Aharonov-Bohm effect, Josephson junctions, SQUIDS, etc.). For students of Lagrangian mechanics, the canonical momentum for a charged particle in an electromagnetic field is given by p = mv + qA. In the relativistic formulation of electrodynamics, A can be written as a 4-vector. As 4-vectors, both of these quantities transform between inertial reference frames according to the Lorentz transformations. Until you come across these situations, probably OK to think of it as nothing more than a mathematical convenience.
