2つ目は、Dictionaryの内容を、キーと値で個別の配列に変えてからソートする方法です。

Dictionary<string, int>
"Dave" 1
"Alice" 2
"Bob" 3
"Eve" 4
"Charlie" 5

→ 変換 →

string[] ⇔ int[]
"Dave" ⇔ 1
"Alice" ⇔ 2
"Bob" ⇔ 3
"Eve" ⇔ 4
"Charlie" ⇔ 5

→ ソート →

string[] ⇔ int[]
"Alice" ⇔ 2
"Bob" ⇔ 3
"Charlie" ⇔ 5
"Dave" ⇔ 1
"Eve" ⇔ 4

Array.Sortメソッドには、キーと値のそれぞれが格納された二つの配列を渡すと、キーの配列に従って対応する値の配列も同時に並べ替えることができるオーバーロードが用意されています。　これを使うことにより、Dictionaryのキーと値の両方を格納した配列を互いに関連付けた状態のままソートすることが出来ます。　KeyValuePairは使わないため、キーが単純型であればソート方法(比較方法)を定義する必要がありません。

この方法によるソートの具体例は次のようになります。

Array.Sortを使ってDictionaryをソートする (キーと値の配列に変換してソートする)
using System;
using System.Collections.Generic;

class Sample {
  static void Main()
  {
    // ソート対象のDictionary<string, int>
    var dict = new Dictionary<string, int>();

    dict.Add("Bob", 3);
    dict.Add("Dave", 1);
    dict.Add("Alice", 2);
    dict.Add("Charlie", 5);
    dict.Add("Eve", 4);

    // キーと値を格納する配列を作成し、Dictionaryの内容をコピー
    var sortedKeys = new string[dict.Count];
    var sortedValues = new int[dict.Count];

    dict.Keys.CopyTo(sortedKeys, 0);
    dict.Values.CopyTo(sortedValues, 0);

    // Array.Sort(Array, Array)メソッドを使ってソート
    Array.Sort(sortedKeys, sortedValues);

    for (var index = 0; index < sortedKeys.Length; index++) {
      Console.WriteLine("{0} {1}", sortedKeys[index], sortedValues[index]);
    }
  }
}
実行結果
Alice 2
Bob 3
Charlie 5
Dave 1
Eve 4

なお、Array.Sortに渡す配列はキーの配列・値の配列の順となっています。　この順序を逆に指定すれば、値でソートできるようになります。