LM7812 and decoupling capacitor value
Ci can be as large as you want.  A 0 impedance input voltage isn't going to hurt the regulator.  In fact, the lower the better.  I'd probably use a 10 &micro;F ceramic, more if the input voltage is of questionable impedance and stability.

What you quote doesn't say what Co needs to be, only what value the rest of the specs are for.  You have to look elsewhere in the datasheet to find the min and max allowed values.  If I remember right (your job to check), the 78xx series regulators are stable with 0 ESR output caps.  The only real limitation is therefore the initial surge current as the output cap is charged up.  Since these regulators protect themselves from output shorts, there is effectively no upper limit from the regulator's point of view.  I'd probably use a 1-10 &micro;F ceramic, depending on what I'm already using in that design.