The primary reasons for the founders creating the dominion, and its rise to power in the Gamma quadrant seems to be a combination of three main factors: superior long-term strategy, the infiltration capabilities of the changelings, and superior technology, particularly in genetics.
We hear multiple stories about changelings suffering persecution in their past. The very term "changeling" was a pejorative term used by solids in the Gamma quadrant. As a result, the founders created the dominion to bring order to the Gamma quadrant and protect themselves:
Female Shapeshifter: Ironic, isn't it? The hunted now control the destinies of hundreds of other races.
Odo: But... why control anyone?
Female Shapeshifter: Because what you can control, can't hurt you.
Odo: How do you justify the deaths of so many people?
Female Shapeshifter: The Solids have always been a threat to us. That's the only justification we need.
Although we do not know precisely the life span of a changeling, we can surmise that it is quite long. First, the female changeling tells Odo, "You are a changeling, you are timeless," which could indicate the changelings are immortal. However, a more concrete minimum lifespan is established in "Children of Time" (Season 5, Ep. 22) in which the Defiant is sent 200 years in the past, and the present day crew meets the descendants of the survivors. Since Odo is still alive, and was already 200 when the incident took place, this would suggest Odo could live to at least 400.
This extended life span was combined with a belief that the solids needed to be controlled at all costs. This affords the changelings the opportunity and perspective to make long term strategic decisions that other races might overlook, have insufficient interest in making, or lack the ruthlessness to implement. In "Statistical Probabilities" (Season 6, Ep. 9), we get the following assessment from Jack,
Yes, yes. That's a typical
Dominion strategy -- they offer to
give up something valuable to hide
the fact that they want something
even more valuable in the long
Even Odo's presence in the Alpha quadrant owes to the long-term planning of the founders. He was sent out with a group of 100 infants, who, according to memory alpha
...were a group of one hundred newly-formed Changelings that the Founders sent out in order to gather information and explore. The Founders did not expect any to return until the late-27th century.
They were intelligence gathering with an eye to eventually encountering being from the Alpha quadrant in 300 years.
Odo's shapeshifting skills are less developed than other changelings. Other changelings are able to perfectly impersonate many races. They manage to get changelings inside Starfleet headquarters, they have a changeling impersonating General Martok for 2 years, they replace Doctor Bashir for 7 weeks without the Deep Space Nine crew realizing, they infiltrate the Romulan Tal Shiar. Not only are their shapeshifting abilities impressive, but their ability to respond as the person they are imitating must be excellent as well. Impersonating Doctor Bashir for a considerable length of time without raising the suspicions of a crew that is specifically looking for changelings would be no easy task.
We can see the power of this infiltration strategy in the Alpha quadrant over the course of only a few years. They manage to set the Klingons and Federation to war without firing a shot, and lead the Romulan Tal Shiar and Cardassian Obsidian Order into an ambush, effectively eliminating them before the fighting in the Alpha quadrant begins. Imagine this sort of capacity played out over centuries or millennia in the Gamma quadrant.
Also, in terms of battle, we never really see what the changelings are capable of. Odo certainly gets defeated, but Odo has a different morality than the other changelings and wouldn't indiscriminately kill solids. The other changelings have no such compunction. Although we don't see specifically what they might do, we meet Lars in "Chimera" (Season 7, Ep. 14), who is able to change into both fog and a fire. That sort of capability would make them very hard to defeat in combat.
Although the Dominion contains many races and species, it is largely run by genetically engineered slave races in the Vorta, and the Jem Hadar.
The Jem'Hadar are cloned on a mass scale with a development cycle that lasts only days to weeks ("The Abandoned", Season 3, Ep. 6). This provides an almost unlimited supply of soldiers, genetically engineered to be completely subservient to the founders, and to be fighting/killing machines. They are a formidable fighting force armed with impressive technology.
The Vorta are certainly less impressive than the Jem'Hadar, but are extremely loyal to the founders, and are able to deal with many situations diplomatically, eliminating the need for the Dominion to waste resources unnecessarily.
Beyond the genetic manipulation technology they must possess, their shield and weapons systems are at least comparable (and at the beginning superior) to Starfleet. This would likely make them the most technologically advanced race in the Gamma quadrant.