SOQL Count distinct occurrences in column

Use COUNT(Id) to get a record count per category.

To order the results, use ORDER BY Category__c DESC.

You can't easily return a count of distinct categories returned, but really all you need here is to count the number of rows returned.