試してみましたか？基本的にリストならLinqはソート順序をキープしてくれますよ。
コレクションによって実装が異なったりするので一概には言えないんですけどね。

しかも安定したソートなので同値であっても順序の入れ替えとかも起きません。
Where使った後OrderByする方が自然ではあるんですが、仮に逆順でもよっぽどのことをしなければ大丈夫です。

// 50,51,52,... 148,149,150
foreach (var number in Enumerable.Range(1, 10000)
    .OrderBy(number => number)
    .Where(number => 50 <= number && number <= 150))
{
    Console.WriteLine($"{number}");
}

// 150,149,148,... 52,51,50
foreach (var number in Enumerable.Range(1, 10000)
    .OrderByDescending(number => number)
    .Where(number => 50 <= number && number <= 150))
{
    Console.WriteLine($"{number}");
}

補足への回答

先にコレクションをソートしておけば大丈夫ですよ。
最初に言った通りWhere句で並び順が崩れるなんていうことは普通ありません。

必要に応じてWhereメソッドを呼び出すというのを何度もやったらいいです。
もしも現在の実装で並び順が崩れるため、パフォーマンスを考えてWhere句の後にOrderByしない解決方法を必要としている場合はコードを添付してください。

// コレクションを最初に作る時にソートしておく
MyCollection = new Collection<MyItem>(DataSource.OrderBy(item => item.Id));

// 入力されたら前後50の範囲を返す関数を作っとく。
public static class MyItemExtension
{
    public static IEnumerable<MyItem> Sampling(this IEnumerable<MyItem> items, int threshold)
    {
        return items.Where(item => (threshold - 50) <= item.Id && item.Id <= (threshold + 50));
    }
}

// 50~150受け取りたい処理にパス
SomeFunction(MyCollection.Sampling(100));
// 250~350受け取りたい処理にパス
SomeFunction(MyCollection.Sampling(300));

パフォーマンス上のことで更に追記

もう一つ。1から10000まで隙間なくデータが埋まっているならWhere句よりGetRangeを使うこともできます。
リストはコピーされるものの、こちらはリスト全体を舐めないですむので場合によっては高速になります。

public static class ListExtension
{
    public static List<T> Sampling(this List<T> items, int threshold)
    {
        // startIndexを計算で求められる場合にはそうする。
        // 1から10000のリストなので追加で1引いた数にすれば良い。
        int begin = threshold - 51; 
        return items.GetRange(begin, 101); // 50 ~ 150は101要素だから。
    }
}

※コレクションによっては最善の方法でキー探索とかしてくれるかもしれませんが、わかりませんしね。。

効率の点からも先にWhereで絞り込んでからソートすればよいと思います。

List<int> list = ...;
int sentinel = 100;
var sorted = list
  .Where(i => i >= sentinel - 50 && i <= sentinel + 50)
  .OrderBy(i => i)
  .ToList();

Whereが順序を保証しないというのはMSDNにはないようでしたがどこに記載されていましたか？
LINQやJavaのStreamやScalaのSeqなどどれも似たようなものだと思っているのですが、複数のスレッドで並行して処理するようにしない限り要素の順序はパイプラインの前段のまま保存されるのが普通だと思ってました。本当はどうなんでしょう・・・

聞きたいことがころころ変わりすぎじゃんね！（笑）
次からは質問する時に自信がなければ変にやりたいことを自分で要約しすぎないようにしましょう。
そもそも1から10000がミクロも関係ない話題ですねこれは…。

もしもコレクションのソースがデータベースで、キャッシュしておけずに毎回SQL問い合わせが発生するようなケース（Webアプリの場合とか）だったらそもそもLinq使うのやめて全部SQL文で対処しましょう。SQL側にも１件だけデータを取ってくるための構文が大体用意されてます。（SQL Serverだったら TOP 1とかね。）

コレクションが固定のマスタでデータをキャッシュしておけるなら、Linqを使えばいいでしょう。
データベースにアクセスするレイテンシを排除することもできますしね。

キャッシュした場合は実現したい検索処理によってどうしたら高速になるのかは変わってきます。
一番簡単な方法であればコレクションをソート済みで用意しておき、Whereメソッドを必要に応じて繋げていき、最も遅い時間を取ってくるのはLastOrDefaultを、最も早い時間はFirstOrDefaultを使えばいいです。

ソートの必要がないように最初にコレクションを用意しておくのはここでもやはり重要です。
まずは時間順でソートしておきましょう。これはSQLならデータを取ってくる時にしておけばいいです。
コレクションをOrderByしたら時間がかかっても、SQLでのソートはインデックスがあれば一瞬です。

SELECT * FROM DATA ORDR BY 時間, 性別;

要素数1万ぐらいならWhereメソッドでフィルターしても全然OKです。
あまりに頻繁に呼ばれるなら色々工夫しなきゃいけなくなりますが、気になるぐらい遅いことはないです。

IEnumerable<T> collection = MyCollection;

if (/*性別を制限するなら*/)
{
   collection = collection.Where(/*性別の制限*/);
}

if (/*最小時間を設定するなら*/)
{
   collection = collection.Where(/*最小時間以上*/);
}

if (/*最大時間を設定するなら*/)
{
   collection = collection.Where(/*最大時間以下*/);
}

if (/* 最も遅い時間をとってくるなら */)
{
    return collection.LastOrDefault();
}
else
{
    // 最も早い時間をとってくるなら
    return collection.FirstOrDefault();
}