Если вы выбираете строки из базы данных через IQuerable и упорядочиваете их по одному столбцу, если в этом столбце есть строки с одинаковым значением, порядок этих строк может отличаться, вам нужно сделать то же, что и сейчас, то есть по двум столбцам: сначала тот, который вас действительно интересует, а затем второй (например, дата), не должно быть такого большого снижения производительности, поскольку сортировка выполняется в базе данных.
Но что нужно сделать, так это указать порядок:
Context.Products
.Where(p => p.ProductID > 100)
.OrderBy(p => p.CategoryID)
.ThenBy(p => p.Date).ToList();
Обратите внимание на ThenBy, который сгенерирует правильный SQL.