Cómo obtener el nivel de jerarquía de esta consulta

Debe agregar una columna llamada Level (o como quiera llamarlo), tanto para el "ancla" SELECT como para la parte recursiva de su CTE, así:

WITH CategoryRec AS 
(
    SELECT Id, Parentid, Name, 1 AS 'Level'
    FROM dbo.Category

    UNION ALL

    SELECT cr.Id, c.Parentid, cr.Name, cr.Level + 1 
    FROM CategoryRec AS cr 
    INNER JOIN dbo.Category AS c ON cr.Parentid = c.Id
    WHERE c.Parentid IS NOT NULL
)
SELECT DISTINCT Id, Parentid, Name, Level
FROM  CategoryRec