Mythic King (Hindu)
Bali was a mighty god-king with quite an impressive pedigree—son of the mighty king Virocana, and grandson of the demonic Hirayakashipu, who had been a very powerful monarch himself, before being defeated by the god Narasinha, who was an avatar or incarnation of Vishnu.
This mighty nobleman's fame spread throughout the world, causing quite a bit of a hubbub amongst the gods. This upstart was becoming more famous than even the great god Indra! Something had to be done.
Enter the mighty god Vishnu—always a clever and tricky sort of fellow. He assumed a dwarfish form and went to see Bali. Calling himself Vamana, the cunning runt went before the great king and begged him for a plot of land three paces wide. Not even suspecting a trick, Bali agreed.
Now, I don't know whether Bali was naive, stupid, or if he just got so many requests for land from magical midgets that he just wound up rubberstamping them without another thought, but this seems like seriously boneheaded move to me. Which, of course, it was. Note to all mythical beings or prospective mythical beings out there: if someone offers you a task or asks you to do something that seems way too simple, such as "Hey, betcha can't lift this tiny kitten!"—this is invariably a trick, and probably won't end in your favour!
But Bali granted little Vamana's silly request (what's he gonna do with a piece of land three strides across, make a very small bowling lane, perhaps?). At that point, the little man revealed himself in all his godly glory, and paced off the entire earth and sky in two mighty strides. He left that third pace for the underworld, and that is exactly where the dim and defeated Bali retreated to.
Bali may have been a sky god in the pre-Vedic times, his worship supplanted by Indra, Vishnu and that crowd. The story of Bali seems to have been told as a sort of humourous tale of the Vedic gods' conquest of this mighty guy (and pretty much his entire family): "See, our god can beat up your god."
References:
Much of this information has been gleaned from a (self-published) book on mythology I have written and am constanly in the process of revising.
Jordon, Michael, "Encyclopedia of Gods" (Facts on File, New York, 1993).