In P&P2, when Lady Catherine arrives at Longbourn in all her splendour, one of her liveried servants is riding the first horse, so I don't think that just seeing someone riding the lead horse would have tipped them off. If I had to choose, I suspect that Britt has come the closest to the right answer - that post horses were obviously in worse shape than privately-owned horses, and probably mismatched as well (though I like Captain Everett's suggestion of shaved, walking advertisements the best ;-).

BTW, I'd like to thank everyone who kept coming up with new solutions to this particular riddle - you at least partly satisfied my "insatiable curiosity"!