When did Mat fight six Aiel? You might be thinking of the men who attacked him in KoD, but a) those weren't Aiel, and b) Thom, Tuon, and Selucia helped. Lan also took out six men on his own in NS where he wasn't nearly as good as he is now.
Well it doesnt say that anywhere exactly, but Mat was fast enough to keep up with the Gholam, which was said to make a Fade look slow, which are in turn described as being quite swift. To me Lan is stronger, but Mat is faster and with longer reach. Mat is also extremely good defensively; in the chapter where the six aiel fought him he knew he couldnt defeat them, so he just blocked their attacks and knocked their hands and defended himself. How many other people could survive against six aiel at once? Essentially, Lan could not get close enough in a one on one to be able to deal any major damage.
It wasn't just six Aiel, it was a dozen, and he didn't so much fight them as he killed one and then held his own long enough to get help from the rest of the Band (which is nevertheless impressive). It happens about halfway through LoC, and they do seem to be trying to assassinate Mat specifically.
I agree with others here who say that the simultaneous smack-down of Gawyn And Galad isn't really a measure of prowess, given that neither of them were really blade-masters at that point, but let's not forget that neither was Mat a great warrior - up until TSR he's just a lucky farmer with a quarterstaff. Those memories of his seriously change the equation. The most attention is payed to the strategic and tactical abilities that come with them, but it's mentioned several times that he subconsciously controls his horse with his knees in accordance to the memories, and at least one mention is given to the fact that, while some of his skill with the ashendarei comes from his familiarity with the staff, the rest comes from his memories. That's important because it means that Mat's integration with what's in his head goes beyond just academic knowledge, it borders on muscle memory and reflex that would otherwise take years of training. Sure, he remembers a lot of generals, but these guys aren't just armchair strategists. Take Aemon of Manetheren. He was a general and a king, but also a warder. You can't tell me he didn't know how to dish out the hurt.
My point is, Lan might have been one of the greatest living warriors in Randland, but as of TSR, Mat very suddenly became hundreds of the greatest dead ones. And I do believe he tends to underestimate himself - after all, we're not entirely sure what Mat is capable of when he's pushed to his limit. Correct me if I'm wrong, but with the exception of getting blasted in Caemlyn, I don't think we've ever seen him beaten.