Changing a crypto map on an established site-to-site VPN router connection to allow new encryption traffic to an Intranet isn't as tricky as it sounds.
Let's assume that an IPsec tunnel is currently being used between the two routers, and currently traffic is using 3DES encryption, but you'd like to use AES encryption for all traffic. When IPsec tunnels (security associations or SAs) are created, the routers (security gateways) at both ends exchange a list of acceptable encryption algorithms for each SA. It is possible for you to add another encryption algorithm to your router's crypto map (IKE proposal) and have your business partner's router continue to select the algorithm you are now using the next time the SA is re-keyed or re-established. Nothing is likely to happen immediately after you update the crypto map -- if something goes wrong, it probably won't occur until the existing SA's lifetime expires. If nothing goes wrong, you still won't see the newly-added algorithm being used until your business partner updates his router's crypto map and the SA is (again) re-keyed or re-established.
What could go wrong? If both routers are the same version of the same product, one of you may "fat finger" the update -- that is, make a mistake in the configuration like removing 3DES from your map when adding AES, or adding AES with a different key length or integrity option, etc. As you probably know from your initial tunnel setup, it's critical that at least one proposal match exactly, and some trial-and-error to reach that point is common. For this reason, it's always a good idea to back up your existing config, make your change at an off-hour, test your change (e.g. by resetting the SA and verifying you can send traffic again), and be prepared to roll back if you fail. Yes, that's disruptive and not a great idea to try on your production VPN during business hours.
If you and your business partner have different routers or use different versions of software from the same vendor, there's also the possibility that interoperability problems will crop up when you first use a new feature. Any interoperability problem is most likely to occur when your business partner changes his router's crypto map because, until that happens, you will probably continue to negotiate the same old algorithm. Again, you should arrange to test this change off-hours and be prepared to rollback both ends if needed. You should also make sure that the tunnel can be re-initiated from BOTH ends -- when you have a proposal mismatch problem, it's not unusual for a tunnel to work when initiated in one direction, but not when initiated in the other. While you might be able to make the change successfully without coordinating a test time with your business partner, it's probably not a good idea.