var results = list.GroupBy(x => x.Category)
.Select(g => g.OrderBy(x => x.SortByProp).FirstOrDefault());
For those wondering how to do this for groups that are not necessarily sorted correctly, here's an expansion of this answer that uses method syntax to customize the sort order of each group and hence get the desired record from each.
Note: If you're using LINQ-to-Entities you will get a runtime exception if you use First() instead of FirstOrDefault() here as the former can only be used as a final query operation.