stonent:
Does the 328 that has never been programmed before work without a crystal like the ATTiny does?
Yes. However, if you use the "burn bootloader" option of the Arduino IDE, then that also sets the fuses; so after that you do need a crystal. If you just use ArduinoISP to program a sketch directly into the atmega328p, then the fuses are not changed and it will run your sketch using the internal oscillator (8MHz with a prescaler of 8, so 1MHz).
from the factory its running at 1mhz, with no bootloader, with an ISP you can set the clcok and install the bootloader (its physical software that sits at the start of flash just like the bootloader to your PC)