Thanks for all the comments. I have one more idea for addressing this. I'm thinking about partitioning my table. Everything that has already been created with the random UUID on one partition and all new, sequential UUIDs on a new partition.

The partition with the old UUIDs will get sorted when I convert it to a CI and there will never be any inserts into it again. All new inserts will go into the new partition where I will ensure the UUIDs are sequential.