The PIC's datasheet says less than 1 Ohm ESR and it specifically mentions tantalum as being OK.
The regulator provides power to the core from the other VDD pins. A
low-ESR (less than 1 Ohm) capacitor (such as tantalum or ceramic) must
be connected to the VCAP pin (Figure 27-1). This helps to maintain the
stability of the regulator. The recommended value for the filter
capacitor is provided in Table 30-5 located in Section 30.0
“Electrical Characteristics”.
http://www.avx.com/docs/Catalogs/techsum.pdf
Has a lot of information about tantalum capacitor failure modes. It's an interesting read.
Steady-State
Tantalum Dielectric has essentially no wear out mechanism and in
certain circumstances is capable of limited self healing. However,
random failures can occur in operation. The failure rate of Tantalum
capacitors will decrease with time and not increase as with other
electrolytic capacitors and other electronic components.
IMO tantalum are fine for this application. I wouldn't be concerned about age unless you have some very special requirements.
If I could get a ceramic capacitor at the capacitance of 10uF and within my voltage requirements, which from my initial searches I can, what problems would I experience if I were to change, if any?
Some circuits (like some linear regulators, for example), require a certain minimum ESR from the output capacitor, which could cause the circuit to oscillate when using a ceramic but not with an electrolytic.
In a precision circuit, a ceramic might not be preferred due to microphonics, but in those cases you probably wouldn't want an electrolytic either.
Otherwise, ceramics are generally preferred. They'll have lower ESR, they're not polarized, they need less voltage de-rating, and so on.
Finally, when searching SMD footprint standards, the common packages seem to be 0402, 0603, and 0805, where they increase in physical size respectively, but also power rating, which suggests to me I should use as large of a package as possible
Usually you choose the smallest package you can get away with because you want to fit as much circuit as you can in the smallest footprint.
Also, for ceramics, the larger sizes (1210 and higher) can have reliability issues because they can be cracked if the board flexes.
Best Answer
Usually they mean they want 10uF in reality, up to you to pick a cap that will deliver, sometimes this really matters, TI rail splitters, looking at you....
I would note that the voltage derating thing is MUCH worse once you get down below about 0603 package size or so, and also when you start using the funkier dielectrics.