Generally these concerns matter in a UI. This automatically means that the amount fetched is going to be very limited.

It might still pose a challenge if you want to support paging or virtual scrolling. But I generally believe in better filtering rather than better sorting.

Sorting is more meant for ranking. Now enums might still offer ranking values. However, these rankings are most likely not alphabetical. For example, bad=0, good=1, best=2, is hardly meaningful to sort on alphabetically. While it would make more sense to be sorted on based on the numerical value.

If the number of rows are small then the client can still easily sort the OData result based on the translated values.

In other words, filtering is better than sorting. Sorting on enums is generally not very meaningful. Unless enums are used for ranking, which means alphabetical sorting wouldn't make much sense. In the off case you do need sorting on enums, you can better do this client side.