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のリストに変換してソートする)
Imports System
Imports System.Collections.Generic

Class Sample
  ' 二つのKeyValuePair(Of String, Integer)を比較するためのメソッド
  Shared Function CompareKeyValuePair(ByVal x As KeyValuePair(Of String, Integer), _
                                      ByVal y As KeyValuePair(Of String, Integer)) As Integer
    ' Keyで比較した結果を返す
    Return String.Compare(x.Key, y.Key)
  End Function

  Shared Sub Main()
    ' ソート対象のDictionary
    Dim dict As New Dictionary(Of String, Integer)()

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

    ' Dictionaryの内容をコピーして、List(Of KeyValuePair(Of String, Integer))に変換
    Dim pairs As New List(Of KeyValuePair(Of String, Integer))(dict)

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

    For Each pair As KeyValuePair(Of String, Integer) In pairs
      Console.WriteLine("{0} {1}", pair.Key, pair.Value)
    Next
  End Sub
End Class
実行結果
Alice 2
Bob 3
Charlie 5
Dave 1
Eve 4

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

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