Thanks for the reply Jayanta.
Yes I've tried renaming the ArcMap normal.mxt and creating a new template - no change.
I tried doing a complete application profile reset as per your link - no change.
I can confirm we have installed service pack 3 for SQL Server 2012, and have indeed upgraded our enterprise geodatabase. We have also re-done all the indexes.
What we've also discovered is that if we load 1 - 2 feature classes into ArcMap - it's ok. If we load more than that, we start seeing the slowdowns I mentioned above.
Also, we've found that when we sort large-ish datasets in Arc Catalog (16,000 records for example) by ObjectID - or anything - it takes a long time. Far longer than it did under 10.3.
At this point - it seems to be something to do with larger amounts of data. Either ArcMap projects loaded with several layers or operations on large-ish datasets. Just viewing a single large dataset in ArcCatalog - no problem.