Even in non-clustered indexes (relevant to pretty much all SQL implementations not just MS SQL Server) random keys can cause the index to balloon over time due to many page splits, requiring extra space or extra maintenance rounds (rearranging the indexes to optimise them occasionally, if the relevant data grows rapidly or changes often).
The effect is just worsened by clustering, as done in SQL Server for significant (or at least measurable) benefits for many data patterns, because your base data is bigger due to wasted space due to excess page splits, as well as your supplementary indexes, so that needs reorganising more often too.
A common answer is to use an int (or maybe bigint) for your internal keys and a UUID for anything external, so you have the benefits of a UUID for external use (practically zero chance of collision in distributed systems, if appropriately random, and not potentially leaking information in some security contexts) but the efficiently of the integer otherwise. Or to use a partially ordered UUID format, which balances the compromises slightly differently (benefit: single value, dropping some of the UUID issues, keeping some of the benefits; detriment: letting some of the disadvantages of UUIDs, potentially reducing some of the benefits).