Inheriting needed when only difference is performed in the constructor?
Based upon your use case, the code below is what I would recommend.  I'm sorry that it is in C#, on this computer I don't have my vb.net loaded so it was easier to express in c#.

There are 3 parts to this.  The class on the bottom should address your needs (KeySet).  the second class helps to make it more easily usable in your code (KeySetHelpers).  The first class (MyExample) is just showing a few ways that you can utilize it.  I think the direct approach is most natural.

Regarding performance and inheritance.  If you follow the process below, I don't think you need another layer of inheritance.  Performance wise, I think that the collection you choose to utilize will matter more than the KeySet.  Since in the end you are just utilizing strings anyway.

One area I would recommend that you look into is the reason why you are flipping the primary/secondary keys based upon which is greater.  Since you are already injecting which is the primary and which is secondary, they should most likely always have the same order when combined.  Otherwise it could complicate the meaning of the key.  Plus if you keep the order primary-secondary and normalize the key by stripping out anything non-alphanumeric and then adding in a parsing token like "-" between the too,...you wouldn't need to store the Key(composite), primary key, and secondary key.  I hope this helps.

public class MyExample
{
    public void Test()
    {
        // Junk Prep
        var primary = System.Guid.NewGuid();
        var secondary = System.Guid.NewGuid();
        var junkData = "blah blah";

        // Real usage
        var keysList = new List&lt;KeySet&gt;();

        keysList.Add(new KeySet(primary, secondary)); // as guid
        // or
        keysList.Add(new KeySet(primary.ToString(), secondary.ToString())); // as guid strings
        // or
        keysList.Add(primary, secondary);// direct as guid


        var keysDictionary = new Dictionary&lt;KeySet, object&gt;();

        keysDictionary.Add(new KeySet(primary, secondary), junkData); // as guid
        // or            
        keysDictionary.Add(new KeySet(primary.ToString(), secondary.ToString()), junkData); // as guid strings
        // or
        keysDictionary.Add(primary, secondary, junkData); // direct as guid

        // etc.
    }
}

public static class KeySetHelpers
{
    #region Lists

    public static void Add(this List&lt;KeySet&gt; keyList, string primary, string secondary)
    {
        keyList.Add(new KeySet(primary, secondary));
    }

    public static void Add(this List&lt;KeySet&gt; keyList, Guid primary, Guid secondary)
    {
        keyList.Add(new KeySet(primary, secondary));
    }

    #endregion

    #region Dictionary

    public static void Add(this Dictionary&lt;KeySet, object&gt; keyDictionary, string primary, string secondary, object value)
    {
        keyDictionary.Add(new KeySet(primary, secondary), value);
    }

    public static void Add(this Dictionary&lt;KeySet, object&gt; keyDictionary, Guid primary, Guid secondary, object value)
    {
        keyDictionary.Add(new KeySet(primary, secondary), value);
    }

    #endregion
}



public class KeySet : IComparable&lt;KeySet&gt;
{
    public KeySet(Guid primary, Guid secondary) { EstablishKey(primary.ToString(), secondary.ToString()); }
    public KeySet(string primary, string secondary) { EstablishKey(primary, secondary); }

    #region Composite Key

    private void EstablishKey(string primary, string secondary)
    {
        if (string.Compare(primary, secondary) &gt; 0)
        {
            Key = primary + secondary;
        }
        else
        {
            Key = secondary + primary;
        }

        Primary = primary;
        Secondary = secondary;
    }

    public string Primary { get; private set; }
    public string Secondary { get; private set; }

    public string Key { get; private set; }

    #endregion

    #region Functional Overrides

    public override bool Equals(object obj)
    {
        return (obj is KeySet) ? Equals((KeySet)obj) : false;
    }

    public bool Equals(KeySet obj)
    {
        return CompareTo(obj) == 0;
    }

    public override int GetHashCode()
    {
        return Key.GetHashCode();
    }

    public override string ToString()
    {
        return Key;
    }

    #endregion

    public int CompareTo(KeySet other)
    {
        return string.Compare(Key, other.Key);
    }

    public static bool operator ==(KeySet obj1, KeySet obj2)
    {
        return obj1.Equals(obj2);
    }

    public static bool operator !=(KeySet obj1, KeySet obj2)
    {
        return !obj1.Equals(obj2);
    }
}