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をソートする (キーと値の配列に変換してソートする)
Imports System
Imports System.Collections.Generic

Class Sample
  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の内容をコピー
    Dim sortedKeys(dict.Count - 1) As String
    Dim sortedValues(dict.Count - 1) As Integer

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

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

    For index As Integer = 0 To sortedKeys.Length - 1
      Console.WriteLine("{0} {1}", sortedKeys(index), sortedValues(index))
    Next
  End Sub
End Class
実行結果
Alice 2
Bob 3
Charlie 5
Dave 1
Eve 4

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