Which columns need index in recursive table and soft delete
Try this index for some noticeable improvement:

CREATE NONCLUSTERED INDEX [CatIndex1] ON [dbo].[Category]
(
    [ParentID] ASC
)
INCLUDE (   [CategoryID],
    [CategoryName],
    [DisplayORder]) 


I am interested in the time reduction. Please let me know your findings.

p.s. consider sorting only once with the ORDER BY if you're running it multiple times. Perhaps put data into a C# DataTable or SQL temp table and sort at the very end of all retrieval operations.