Using the SI in electromagnetism makes it a pretty complicated subject ;-)). Anyway, let's try
The Coulomb force between two point particles (magnitude) in SI units is
$$F=\frac{q_1 q_2}{4 \pi \epsilon_0 r^2}$$
So the dimension for the conversion factor ##\epsilon_0## is
$$[\epsilon_0]=[Q^2 /(r^2 F)]=\text{C}^2 \text{s}^2/ (\text{kg} \; \text{m}^3).$$
Here it's the force between two pieces of current conducting wire defining
$$F=\mu_0 I_1 I_2 L/d \; \Rightarrow \; [\mu_0]=[F/I^2]=\text{kg} \; \text{m}/\text{s}^2 \cdot \text{s}^2/\text{C}^2=\text{kg} \; \text{m}/\text{C}^2.$$
and thus finally
$$[\epsilon_0 \mu_0]=\text{s}^2/\text{m}^2$$
which is the dimension of an inverse squared speed.
Manipulating the free Maxwell equations a bit you get the wave equation
$$(\mu_0 \epsilon_0 \partial_t^2-\Delta) \vec{E}=0,$$
which shows that the phase velocity is indeed ##c=1/\sqrt{\epsilon_0 \mu_0}##.
It's now also very clear that all there is for the vacuum permittivity and permeability is that they are fixed constants defining the system of units: ##\mu_0## is fixed by the definition of the Ampere, i.e., the unit of the electric current. ##c## is fixed through the definition of the unit of length, metre, via the definition of the second, and thus also ##\epsilon_0## is fixed by just the definition of the SI for time, length, mass, and electric current.
Of course, in the medium ##\epsilon=\epsilon_0 \epsilon_r## and ##\mu=\mu_0 \mu_r## are parameters from the constitutive equations of the medium. They are not so fundamental since they are defined from the microscopic theory via linear-response theory, i.e., they are related to the description of the medium for weak em. fields.