For the uart, just change baudcon (or its equivelant) to manually adjust the baud rates to maintain your clock speed. There are easy to read charts in the datasheets.

In my apps, I set up a sub for each clock speed I run at, and then gosub the appropriate sub each time I need to change clock speed. Each subroutine sets the osccon, baudcon, and any other delay related variables so all of my routines behave the same regardless of the actual running speed.

For timed delays, you will have to either adjust the parameter, or make your own delay routines that use your own parameters. (For instance, instead of the built in delayms you would use a gosub DelayCorrectedms, which loops and calls delayus with an adjusted time...keeping in mind the added overhead of the basic code.)