Delete / modify entries in Remote Site Settings if you don't want to perform certain callouts.
Disable "Big Deal Alert" on Opportunities - can be embarassing to send an email with "My awesome test Opp !!1" to CEO
If you have managed packages with API keys (like FinancialForce) - ask their support teams to regenerate the keys
If you have "power users" that will coordinate User Acceptance Testing - create entries in Delegated Administration area so they can "login as"
(since Spring '13)
If you want to see the "send an email" button on Activities related list or wonder why you don't get any notifications from approval processes - set Email Deliverability to "All Email"
(since Spring '16)
Consider implementing SandboxPostCopy to automate steps in Apex after a sandbox is copied.
Specific for full sandboxes
break Email addresses on Contacts, Leads etc. with suffix like it's done for users (and wherever you store email info if there's any risk of routine communication kicking in for example from workflow email alerts)
disable Weekly Data Export?
if you have email templates or documents with sensitive data (like Purchase Order and scanned signature of approver) it might be worthwhile to cripple them somehow (fake logo, big red "TEST ONLY" etc..). Documents won't be carried to non-full sandboxes though
Another thing I have implemented is a custom setting referenced in workflows & triggers to determine whether to perform various actions (specifically sending emails)
something similar to this:
It was a bugger to get implemented since there were tons of workflows, triggers, and controllers to update. Now I'm very glad I took the time to do it. You have to remember to set default org values though since custom settings don't get populated in a sandbox refresh. As of Summer 13 custom settings get copied to sandboxes.