The smaller a 'regular', stellar-mass black hole is, the denser it is inside of its event horizon, correct?
Yes, that's correct. But the black hole density is a mean density, that is, it's just the mass of the BH divided by its Schwarzschild volume. It's not like there's a uniform ball of stuff inside the event horizon with that density.
I have also read that if you cross the event horizon of a supermassive black hole, you would not be immediately 'spaghetti-fied', because of the low densities on the outskirts of those black holes....
A BH is mostly empty space. Anything that crosses the event horizon rapidly falls towards the centre. As I mentioned in this answer:
We cannot say exactly what happens at the core of a black hole. As discussed in this answer by Florin, we need a theory that unites General Relativity and Quantum mechanics to answer such questions.
A pure GR black hole has a mathematical singularity at its core, but most astrophysicists believe that's unphysical, and that a proper quantum gravity theory will eliminate that singularity. However, it's likely that the core of a black hole is still very small, since the quantum gravity corrections probably don't become significant until the size gets smaller than an atom.
So if a BH isn't actively accreting material, the density in its outskirts, either side of the event horizon, is zero. However, a BH with high density will spaghettify you before you cross the event horizon. You get spaghettified by the tidal force caused by the differential gravitational acceleration: if you're falling feet first towards the BH, the acceleration at your feet is greater than the acceleration at your head, so it feels like you're being pulled apart. A big BH actually has more tidal force than a small BH at the same radial distance (i.e., the distance to the centre of the BH), but a SMBH has such a large Schwarzschild radius that you have to be well within the event horizon before the tidal force is dangerous.
There are more details about spaghettification in this Physics answer by Andrew Steane. And here's a short live Python program that calculates the radial distance where a 1 m steel rod (falling vertically) would be pulled apart by the tidal force.
Eg, with a 3 $M_\odot$ BH, which has a
Schwarzschild radius $r_s$ of 8.860 km, the steel rod would break at a distance of 112.176 km = 12.661353 $r_s$.
A tiny black hole with an event horizon less (far less) than a millimeter is going to be a septillion times or more denser than the moon, not just a million, correct?
Correct. BH mass is proportional to $r_s$, so the mean density is inversely proportional to the square of the mass or radius. Eg, a 1 mm BH has a million times the density of a 1 m BH.
The relevant equation for the mean density is
$$\rho = \frac{3c^2}{8\pi G{r_s}^2}$$
and the Schwarzschild radius is
$$r_s = \frac{2GM}{c^2}$$
You can get BH density & various other parameters of a Schwarzschild BH from the Hawking radiation calculator. FWIW, $r_s$ for the Earth is ~8.870056 mm.
Unless Hawking radiation lowers the density, not just the mass....
No, Hawking radiation doesn't do that. As the BH loses mass, it continues to obey the above equation. It might do something odd when it has lost almost all of its mass, but we need a quantum gravity theory for that.