Hello,
Both circuit have strong dependence on HFE (that varies per device [see data sheet]) and with temperature), so your Vce will not be half the supply (or somewhat above for the upper circuit).
The lower circuit will have significant distortion, especially when driven from a voltage source. When you have significant swing (but not saturating), you will even notice that on the oscilloscope graph.
The first circuit may have significantly less distortion when RE >> 1/(40*Ic).
re (1/(40*Ic)), is not a real resistor that is in the collector, but relates to the transconductance of the transistor (ic/vbe small signal). The saturation voltage can be very low (100mV or even less).
Look in to the datasheet of many transistors. Especially at low collector current (were bulk resistance doesn't introduce additional voltage drop), Vcesat can be very low. The modern multi cell low Vce-sat transistors (NXP, Zetex/Diode) can have saturation voltages in the 10mV range.