Substition of electrolytic capacitors in surface mount applications
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.