removal of GUIDS used for all PK's, FKs & Clustered indexes
(Moving discussion to answer)

First of all, you have to ask yourself: Why go after GUID first (if at all)? You could end up spending a lot of time rearranging tables and gain no benefit at all.

What do we know:


You state that the queries are generated by NHibernate. This indicates that you are an OLTP system.
Your major waits are CXPACKET and PAGEIOLATCH
Query plans are not doing what you want them to do


None of the above indicate that changing away from GUID is the best thing to do here. Here is why: 

First, while moving away from GUID might reduce fragmentation - this has no effect on your query plans (Statistics has). As a matter of fact, it may even make things worse since you will now have to deal with the ascending key problem described here: http://blog.kejser.org/2011/07/01/the-ascending-key-problem-in-fact-tables-part-one-pain/ which will cause your parallel queries to run single threaded.

Second, the presence of CXPACKET as a high wait indicates that you are running a lot of parallel queries. This indicates that you are getting wrong estimates or are lacking indexes - GUID's wont help with that either (and lowering DOP is not the answer here)

Third: Even if you did manage to switch to GUID and using your 20M row example, how much would you actually save? Every row would be 12B bigger (unless you use a heap of course, but that has to be understood well first). There are 20M row them - this is 240MB of RAM (assuming of course, that the pages are full, which they only will be on the keys, not the secondary keys). 10 times that is just over 2GB, which today costs less than one hour of quality DBA consulting. In other words: trying to squeeze more space out of the pages is throwing money and your precious time out the window.

In your situation, it sounds like you need to collect some data from sys.dm_exec_query_stats and try to find out where the poor performance is really coming from. Since this is NHibernate, I would look out for:


Poorly parameterised queries (can be fixed with simple hints or better stats)
Over indexing or lacking good covering indexes
Lacking join conditions
Optimiser chosing hash join when loop would be better (you can use OPTION (LOOP JOIN) temporarily to see if a good loop join plan is even possible)


The best way to remove PAGEIOLATCH is not to squeeze more into memory (unless the database is very small or you can just buy cheap RAM) - it is to avoid doing bad table scans in the first place.