Идея получает анонимный объект с элементом и случайным порядком, а затем переупорядочивает элементы этим порядком и возвращает значение:
var result = items.Select(x => new { value = x, order = rnd.Next() })
.OrderBy(x => x.order).Select(x => x.value).ToList()