1つ目は、Dictionaryの内容を、KeyValuePairのリストに変えてからソートする方法です。

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

→ 変換 →

List<KeyValuePair<string, int>>
{"Bob", 3}
{"Dave", 1}
{"Alice", 2}
{"Charlie", 5}
{"Eve", 4}

→ ソート →

List<KeyValuePair<string, int>>
{"Alice", 2}
{"Bob", 3}
{"Charlie", 5}
{"Dave", 1}
{"Eve", 4}

KeyValuePairはDictionaryの内部で使われている構造体で、キーと値のペアを一つの構造体として格納するためのものです。　Dictionaryを直接列挙する場合などにも使われます。　DictionaryをこのKeyValuePairのリストに変換してから、List.Sortメソッドを使ってソートします。

ただし、ただ単にKeyValuePairをソートしようとしてもKeyValuePairはそのソート方法が定義されていないため、List.SortメソッドはInvalidOperationExceptionをスローします。　このため、KeyValuePairのソート方法(比較方法)を定義したメソッドを別途用意し、ソートする際にList.Sortメソッドに渡す必要があります。

この方法によるソートの具体例は次のようになります。　この例におけるCompareKeyValuePairメソッドが、KeyValuePairのソート方法(比較方法)を定義するメソッドです。

List.Sortを使ってDictionaryをソートする (KeyValuePairのリストに変換してソートする)
using System;
using System.Collections.Generic;

class Sample {
  // 二つのKeyValuePair<string, int>を比較するためのメソッド
  static int CompareKeyValuePair(KeyValuePair<string, int> x, KeyValuePair<string, int> y)
  {
    // Keyで比較した結果を返す
    return string.Compare(x.Key, y.Key);
  }

  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の内容をコピーして、List<KeyValuePair<string, int>>に変換
    var pairs = new List<KeyValuePair<string, int>>(dict);

    // List.Sortメソッドを使ってソート
    // (引数に比較方法を定義したメソッドを指定する)
    pairs.Sort(CompareKeyValuePair);

    foreach (var pair in pairs) {
      Console.WriteLine("{0} {1}", pair.Key, pair.Value);
    }
  }
}
実行結果
Alice 2
Bob 3
Charlie 5
Dave 1
Eve 4

List.Sortメソッドは、CompareKeyValuePairメソッドで定義されている比較処理にしたがってソートを行います。　上記の例ではキーを比較したため、Dictionaryはキーを基準にソートされました。　比較方法の定義を変えればソートの順序を変更することもできます。　例えば、CompareKeyValuePairを次のように変更することにより、Dictionaryを値でソートできるようになります。

List.Sortメソッドと比較方法の定義(Comparison<T>デリゲート)については、複合型のソート・複数キーでのソートで詳しく解説します。