Погуглил немного готовые реализации — ужас какие неэффективные! Пришлось набросать свою, там всего-то пара строк кода, но вдруг кому-то пригодится.

[TestFixture]
public class NaturalComparerTest
{
   readonly NaturalComparer cmp = new NaturalComparer();

   [Test]
   [TestCase(null, "")]
   [TestCase("", "a")]
   [TestCase("a", "aa")]
   [TestCase("3", "4")]
   [TestCase("3", "34")]
   [TestCase("3", "a")]
   [TestCase("a3", "a4")]
   [TestCase("a3", "b3")]
   [TestCase("a34", "a34b")]
   [TestCase("AK47", "AK74")]
   [TestCase("I-9", "I-10")]
   [TestCase("5-out-of-8", "5-out-of-20")]
   [TestCase("5-out-of-8-apples", "5-out-of-20-apples")]
   [TestCase("episode-1-part-1", "episode-1-part-2")]
   public void TestLess(string x, string y)
   {
      Assert.IsTrue(cmp.Compare(x, y) < 0);
   }

   [Test]
   [TestCase(null, null)]
   [TestCase("", "")]
   [TestCase("a", "a")]
   [TestCase("4", "4")]
   [TestCase("43", "43")]
   [TestCase("a-43", "a-43")]
   [TestCase("43-a-34", "43-a-34")]
   public void TestEqual(string x, string y)
   {
      Assert.AreEqual(0, cmp.Compare(x, y));
   }
}


public class NaturalComparer : IComparer<string>
{
   public int Compare(string x, string y)
   {
      if (x == null && y == null) return 0;
      if (x == null) return -1;
      if (y == null) return 1;

      int lx = x.Length, ly = y.Length;

      for (int mx = 0, my = 0; mx < lx && my < ly; mx++, my++)
      {
         if (char.IsDigit(x[mx]) && char.IsDigit(y[my]))
         {
            long vx = 0, vy = 0;

            for (; mx < lx && char.IsDigit(x[mx]); mx++)
               vx = vx * 10 + x[mx] - '0';

            for (; my < ly && char.IsDigit(y[my]); my++)
               vy = vy * 10 + y[my] - '0';

            if (vx != vy)
               return vx > vy ? 1 : -1;
         }

         if (mx < lx && my < ly && x[mx] != y[my])
            return x[mx] > y[my] ? 1 : -1;
      }

      return lx - ly;
   }
}