Nit, I think this is more readable:

As this way the code reads as: if a is shorter...

I read what I wrote as "if the first different character is at the end of a.data".

I think yours requires to be thinking about longer and shorter, which I'm not at this point.

I understand from if firstCharDifferent == len(shorter) { that firstCharDifferent actually lost its value, as it's not first char different now, but a signal saying: _ all common characters are equal, pending to check whether one string is longer than the other one._

Which now makes me think that it would be better to just write:

	if firstCharDifferent == len(shorter) {
		return compareLengths(a.data, b.data)
	}
	// ...
}
// ...

func compareLengths(a, b []string) int {
	switch {
	case len(a) == len(b):
		return 0
	case len(a) < len(b):
		return -1
	case len(b) > len(a):
		return +1
	}
}

Both options are fine to me, but I agree with @colega naming of firstCharDifferent is indeed misleading (premature - it might be just all equal characters. Perhaps keeping i and not introducing new var might help here?

Oh great, so maybe then just:

if i == len(shorter) {
    return len(a.data) - len(b.data)
}
firstCharDifferent := i

Since decodeSize is very cheap, we can keep decoding sizes as we go, like:

So then later we can just do i = lastLblStart.

This gives pretty good performance impact:

goos: linux
goarch: amd64
pkg: github.com/prometheus/prometheus/model/labels
cpu: 11th Gen Intel(R) Core(TM) i7-11700K @ 3.60GHz
                                  │ bryanagain  │              tracknoloop               │
                                  │   sec/op    │   sec/op     vs base                   │
Labels_Compare/equal-16             25.59n ± 0%   26.48n ± 3%   +3.46% (p=0.000 n=30+10)
Labels_Compare/not_equal-16         30.25n ± 1%   24.07n ± 3%  -20.43% (p=0.000 n=30+10)
Labels_Compare/different_sizes-16   16.46n ± 1%   12.38n ± 8%  -24.84% (p=0.000 n=30+10)
Labels_Compare/lots-16              47.77n ± 1%   42.97n ± 4%  -10.06% (p=0.000 n=30+10)
geomean                             27.94n        24.13n       -13.63%

I've ran this benchmark multiple times and didn't get a consistent result (I was getting the equals benchmark faster in my version, which doesn't make sense), however I also think that if we do this, we can remove the last for loop (as we already know which labels are different, no need to search for them).

I would like to search for the first difference much faster, e.g. 8 bytes at a time using dwords, or even longer strides using SIMD. I made various attempts at this, e.g. 06f8bc7. I think it's faster than your version, although I don't really like the implementation in github.com/grailbio/base/simd.FirstUnequal8Unsafe.

Putting an extra if-statement inside the tight loop does not seem attractive.

If we're going unsafe, then why just not cast the 8 bytes to uint64?

That seems to give pretty good results:

goos: linux
goarch: amd64
pkg: github.com/prometheus/prometheus/model/labels
cpu: 11th Gen Intel(R) Core(TM) i7-11700K @ 3.60GHz
                                  │   original   │            unsafe_uint64            │
                                  │    sec/op    │   sec/op     vs base                │
Labels_Compare/equal-16             24.635n ± 0%   5.832n ± 2%  -76.33% (p=0.000 n=10)
Labels_Compare/not_equal-16          30.33n ± 1%   14.37n ± 1%  -52.63% (p=0.000 n=10)
Labels_Compare/different_sizes-16   16.125n ± 1%   5.353n ± 2%  -66.80% (p=0.000 n=10)
Labels_Compare/lots-16               47.39n ± 0%   27.50n ± 2%  -41.97% (p=0.000 n=10)
geomean                              27.49n        10.54n       -61.66%

I included your latest code, and updated my benchmark results.
Now mostly going faster than the slice version.

Both options are fine to me, but I agree with @colega naming of firstCharDifferent is indeed misleading (premature - it might be just all equal characters. Perhaps keeping i and not introducing new var might help here?