"League" is an old measurement of distance. It was mainly used at sea and represented about 3 nautical miles. http://en.wikipedia.org/wiki/League_(unit) Imagine two people racing each other. If one is far ahead of the other, then he is doing better when compared to the other person. So, when comparing Thai food against all others, saying it is "leagues" better implies that Thai food is much better than all other food.

Leagues means "many times." That's because a "league" is a section that is supposedly very different from another league, and to say something is "leagues different" can only be an emphasis to the distance in difference (being long in distance, thus making it greatly different).