You could definitely script something in Python (or similar) to make the task easier.
Rather than comparing every featureclass with every other featureclass recursively, partition them into point, line and polygon categories.
Within each category, calculate the number of features in each layer. This gives you another sub-category (eg point featureclasses with 12,345 features) which should hopefully only contain a few potential duplicates.
You can then use PolyGeo's suggestion of the Feature Compare Tool on each combination of featureclasses in the sub-category, flagging the suspected duplicates.
EDIT:
You should probably also consider that there might be different versions of the same featureclass (eg, a newer version of the Roads database). So another test would be for duplicate schemas.
The Geodatabase Diagrammer might help to give an overview of the different featureclasses. You could also export to XML and parse the schema using your own script to find duplicate/similar schemas.
Still another idea is to throw this back to your users. "Archive" the existing bloated geodatabase and take it offline. Then ask your users which datasets they really need - make them come to you when a dataset they need isn't available.
You'll probably find that of the thousands of featureclasses, most aren't really necessary.