Don't forget in DS9, they had stolen the schematics to the USS Defiant and later on, kidnapped O'Brien and other DS9 crew to make it work and fight against the Klingons, so not only did they have a good ship, the had an advanced ship design/technology. They also had perfected the ability to transport back and forth between the universes, so acquiring more tech would not be too farfetched.