Кажется, мне не хватает чего-то тривиального.

Во всяком случае, здесь это идет:

var order = new[]{1,3,2};
var foos = new[]{new Foo{Id=1}, new Foo{Id=2}, new Foo{Id=3}};

Как отсортировать foos по порядку массива с помощью Linq?

Желаемый результат:

foos == new[]{new Foo{Id=1}, new Foo{Id=3}, new Foo{Id=2}};

Редактировать:
Заказ содержит идентификаторы Foo. Извините, что я не упомянул это. Иногда еще сложнее правильно задать вопрос, чем ответить на него. :)