My first approach for 2 strings would be a binary search. If each string is of length L, start by comparing the substrings from 0 to L/2. Then, depending on whether they match, either compare the substrings to L/4 or 3L/4, etc. This should give the correct result in log_2(L) steps, but bear in mind that each step requires 2 substring ops which may not be particularly cheap.

For the large number of pairs of strings consisting of only 2 chars "a" and "b" I'd think about assigning them into hash bins based on initial char sets. Each set you create should halve the number of other operations.