removal of GUIDS used for all PK's, FKs & Clustered indexes

Inherited control over a database that has this nasty config. It also has large sections of code generated by NHibernate, including the gneeration of GUIDs before they get to the db so no chance of using NEWSEQUENTIALID() either. Obviously changing some of these sounds like a huge piece of work, but changing the Lookups doesn't sound too painful. I've documented the fragmentation and CL width and NC indexes built from these, optimizer choosing incorrect plans, etc.. but tasked with a workaround i'm coming up a bit short. My current plan is to investigate how much is possible to change and in the interim add an identity field to the main heavily indexed tables and make that the clustered index and keep the GUIDs as PK's. Is this the best I can hope for? or not even worth it? any other workarounds that i have omitted ? Thanks