Adding a Clustered index to a HEAP table on someone else's app
I'm going to go on the assumption that you've identified a problem that needs to be fixed... though I'm not entirely convinced of that yet.

Similar to my answer here, there are two cases when it comes to vendor applications. 


The application is currently under license and/or the vendor/owner doesn't want you meddling.

In this case, definitely do not change the schema in any way, including adding indexes of any kind.

Making schema changes may in fact void your license contract, but this can also cause problems for the vendor if they decide to fix the issues in a future schema update. Speaking from personal experience from the point of view of the vendor, we sometimes have to very actively tell clients to stop creating objects in our databases, because it impacts our ability to successfully apply schema changes. (I'm not just saying that -- we had a case a couple months ago where a schema update failed for one client because of an unexpected dependency from a client-created object. Slightly different scenario than adding an index, but still, it does come up.)

There are rare cases where database-level changes are okay, but you need to make absolutely certain the vendor is okay with what you're planning to do.

The best option for this scenario is... actually, not to make any changes yourself. Put together a compelling case to prove why it's important these changes be made, and present it to the vendor for them to implement in a future release.

From a vendor's point of view, ideally suggestions are specific, simple to implement and test, and have a high positive impact for all clients. In a large application, suggesting that all tables that are heaps be converted to clustered indexes may be (and probably is) a good idea, but it's a complete non-starter. Instead, figure out the top 5-10 most important tables or 2-3 application areas that would benefit from this type of change in your environment.
The application is out of license or the vendor/owner doesn't care what you do with it.

In this case, you can add any index you want, but objects should remain in place with the same names (note I didn't say the same objects). There are many options here, depending on how the application and database works internally. If you still plan to apply future vendor-supplied schema changes, tread very carefully and make sure you create undo scripts for all your changes.

The key to successfully making changes is to maintain application functionality... easier said than done, of course, if you plan to make significant changes.

That said, simply adding clustered indexes is pretty safe. The challenge will be selecting an appropriate key for each index, and this should be done by hand, not automated. The only way to do this part well is by familiarizing yourself with a table's access patterns and purpose.

Come to think of it, you could go through the same process as in the other case: identify the 5-10 tables that would have the highest overall impact, and fix those first. You may find that's all that needs to be done.


Edit: this answer, in a more general sense, is now available in video form.