Physically, what is the magnetic vector potential?
There is an analogy between the electric scalar potential and the magnetic vector potential, which is not usually explicitly taught to undergrads. I believe that if you understand this analogy, the magnetic vector potential will seem as natural and intuitive as the electric scalar potential.
The physical meaning of the electric scalar potential is usually considered to be potential energy per unit charge. The physical meaning of the magnetic vector potential is actually very similar: it's the potential energy per unit element of current. By "element of current" what is meant is a quantity with the units of current times length; it's the current through a piece of wire times the length of the wire, with the direction of conventional current. Accordingly, the units of the magnetic vector potential are joules per ampere-meter in SI.
If we have some system of stationary charges and steady currents flowing through stationary wires, we can ask: what is the total electromagnetic potential energy of this system? (We ignore the kinetic energy of the electrons flowing through the wires.) The answer to this is well-known, and it's given by the formula \[U_e = \frac{1}{2} \int \rho \phi \, \mathrm{d}V\] This formula justifies the idea that the electric scalar potential is energy per unit charge. [1] \(\rho \, \mathrm{d}V\) is an infinitesimal element of charge, multiplying it by \(\phi\) gives the energy, and we sum over all charges in the system. It also shows that the energy required to assemble a charge distribution doesn't depend on how the charges got there (provided there's no friction). We know this must be true because energy is conserved, but this formula demonstrates it explicitly.
There's also magnetic potential energy. It takes energy to fire up a current in a wire because of the wire's self-inductance: increasing the current induces a back emf and you have to pump energy into the system in order to overcome it. It also takes energy to reposition two current-carrying wires relative to each other as they exert magnetic forces on each other. We would like to have a formula for the magnetic potential energy similar to the formula for \(U_e\) above. It shouldn't depend on how the currents got there; it should only depend on the final configuration.
Note that the magnetic potential energy in the final configuration necessarily depends not only on the amount of current but also the direction it is flowing in. For example, if we take two equally sized circular loops of wire, and orient them so that they are parallel and coaxial, like in this diagram:
We know there's an attractive magnetic force between them, so if we brought in the top loop (for example) from spatial infinity, as it approached the bottom loop, it would lose potential energy. On the other hand, if the top loop had current circulating in the opposite direction, the force would be repulsive, and the potential energy would increase as it was brought in from spatial infinity. So the two configurations, differentiated only by current directions, would have different energies.
Now if we have an infinitesimal element of current, which we can write as \(I \, \mathrm{d}\mathbf{l}\) or \(\mathbf{J} \, \mathrm{d} V\), it's electrodynamically equivalent to the superposition of three axis-aligned elements:\[\mathbf{J} \, \mathrm{d}V = J_x \hat{\mathbf{x}} \, \mathrm{d}V + J_y \hat{\mathbf{y}} \, \mathrm{d}V + J_z \hat{\mathbf{z}} \, \mathrm{d}V\] And the amount of energy it takes to bring in an axis-aligned current element from infinity may vary depending on direction, so at each point, instead of a single constant like the electric scalar potential, we need three constants, one per direction, so that \[\mathrm{d}U_m = a J_x \, \mathrm{d}V + b J_y \, \mathrm{d}V + c J_z \, \mathrm{d}V\] We can combine the three constants into one vector and express this result using the dot product. Since this vector is the magnetic analogue to the electric scalar potential—it tells you the potential energy per unit element of current—you might expect that it's the magnetic vector potential. And we can show that this is indeed the case (again, modulo a factor of 2 for double-counting). The final result is \[U_m = \frac{1}{2} \int \mathbf{A} \cdot \mathbf{J} \, \mathrm{d}V\] and the total energy of the configuration is \[U_{em} = \frac{1}{2} \int \mathbf{A} \cdot \mathbf{J} + \rho \phi \, \mathrm{d}V\]
So as I said before, just as the electric scalar potential is potential energy per unit charge, the magnetic vector potential is potential energy per unit element of current. But current has a direction, so the magnetic vector potential has to have three components. That's why it's a vector too.
The interpretation of the magnetic vector potential as potential energy per unit element of current can be taken further in Lagrangian mechanics. The Lagrangian for a nonrelativistic charged particle in an electromagnetic field is \[L = T - q\phi + q\mathbf{v} \cdot \mathbf{A}\] Note that \(q\mathbf{v}\) is an element of current.
However, you really do need Lagrangian mechanics in order to make sense of velocity-dependent potentials—the nice Newtonian picture with force as the (negative) gradient of potential energy does not apply here. I suspect this is why this meaning of magnetic vector potential is not really explored in intro electrodynamics for undergrads—such courses, at least in North America, usually presuppose knowledge of only Newtonian mechanics.
The magnetic vector potential also has a deeper meaning, but you need to understand quantum mechanics in order for it to make sense to you. It's the phase shift per unit charge that a charged particle picks up as it moves through space. That is, if a particle with charge \(q\) moves along a path from one point to another, the magnetic vector potential causes the phase of its quantum-mechanical wave function to change by \[\Delta \varphi = \frac{q}{\hbar} \int \mathbf{A} \cdot \mathrm{d}\mathbf{x}\] This can be directly observed in the Aharonov–Bohm experiment.
Note that the electric scalar potential is the phase shift per unit charge that a charged particle picks up as it moves through time. This is pretty clear since the electric scalar potential times charge is potential energy, and the Schrödinger equation tells us that energy of the particle is the rate at which its phase evolves with time, modulo a factor of h-bar. So the magnetic vector potential bears the same relationship to space as the electric scalar potential bears to time. (In fact, in relativity, we see that the electric scalar potential forms the time component, and the magnetic vector potential the space components, of a four-vector, called the electromagnetic four-potential.)
[1] Why the factor of one-half? Because when we integrate over all space like this, we're double-counting each pair of charges.