Это на самом деле задумано. Для реализации управляемой сервером подкачки страниц (SetEntitySetPageSize это позволяет) требуется стабильный (и общеизвестный) порядок результатов.
Таким образом, служба упорядочит результаты вашей работы службы (она также делает это с наборами сущностей) по всем ключевым свойствам данной сущности.
Клиент может в некоторой степени влиять на порядок - если в запросе есть $ orderby, результирующим заказом будет применение $ orderby, за которым следуют все ключевые свойства.
В настоящее время на сервере нет способа прописать порядок для набора сущностей или операции службы, чтобы обработка пейджинга, управляемого сервером, учитывала его так же, как и с $ orderby от клиента.
Вы можете либо заставить своего клиента добавить правильный $ orderby, либо, если это невозможно, единственный другой обходной путь, о котором я могу подумать, - это вставить $ orderby в URL, прежде чем он будет обработан службой данных WCF (это можно сделать через пользовательский хост , специальные заголовки, WCF, ... зависит от того, как именно вы размещаете службу и тому подобное). Но это немного странно и требует от вас полуразбора URL, чтобы иметь возможность распознать любой существующий $ orderby, уже находящийся там.
Обратите внимание, что это поведение не только для подкачки, управляемой сервером, также $ top и $ skip переупорядочивают результаты для поддержания стабильного порядка.