Error: FATAL_ERROR|System.LimitException: Apex CPU time limit exceeded

The records basically come into my trigger code at Step 7 here (who knows if this is up to date):
https://developer.salesforce.com/docs/atlas.en-us.apexcode.meta/apexcode/apex_triggers_order_of_execution.htm

And the CPU limit shows it is over the limit as soon as it hits my package.
Maximum CPU time: 13170 out of 10000 ******* CLOSE TO LIMIT

At this point as an App Builder what the heck can I do? The user doesn't seem to understand I can't controll all the workflows they have setup. Of course the error email they get is right when it comes into my package and tries to run the first line so it looks like I'm the cause and Salesforce Support just tells them the same thing so it is futile to argue. Even running a limit check to see if the limits are blown throws the exception