The tables sound like good candidates for havaing their non-clustered PK converted to a clustered PK.

I'd like to expound on a couple points in your post.

This is not always true. The first part is, i.e. when a table has a clustered index the clustering key is written to the leaf pages of all non-clustered indexes so that if more data than is in the non-clustered index leaf page is needed to satisfy the query the engine can get back to the data row (i.e. the clustered index entry) to retrieve it. However the latter part is not always true. With heaps the leaf pages of the non-clustered index still need a way to get back to the entire data row (in this case a page in the heap) if more data is needed to satisfy the query, but since there is no clustering key SQL Server stores what is called the RID (Row Identifier) from the row in the heap in the leaf page of the non-clustered index. RIDs are actually 8 bytes so if your PK is less than 8 bytes then you would actually have a space savings and not a space increase in your non-clustered indexes.

Any query plans that reference the table will be negated by the schema change. This means queries against these tables will need new plans to be compiled the next time they are executed. On a busy system lots of recompiles can hurt until all commonly used plans are again cached. SQL Server will definitely use some different query plan operators (e.g. RID Lookups become Bookmark Lookups, Table Scans become Clustered Index Scans, etc.) after the table has had its PK converted to a clustered PK although I would not expect there to be a drastic change in performance one way or the other for queries that were already covered by the set of indexes prior to the change.

One other benefit of switching to a clustered index will be that you no longer need to worry about forwarded records. In a heap, when an existing row is updated and that row no longer fits on the page where it lives a forwarding record is created to hold that row and a pointer to that new record is placed in the old page. If the same record is updated again later and the same process occurs again you now have to visit 3 pages to get to that row. Long chains of forwarded record pointers can affect performance and there is no great way to alleviate them. In SQL 2008 you would use ALTER TABLE REBUILD but if you find yourself wanting to do that to a heap then you should be considering adding a clustered index.

Run this during off-hours or a maintenance window as it can impact performance and see the forwarded_record_count column:

SELECT *

FROM sys.dm_db_index_physical_stats(DB_ID(), OBJECT_ID('dbo.YourHeap'), NULL, NULL, 'DETAILED');

If you decide to add the clustered index I would recommend doing it in this order:

- drop all non-clustered indexes and the PK

- add the PK as clustered

- re-add the rest of the non-clustered indexes