Non-Canon answer (its based on evidence from Star Trek Online)
In the 2410s, Starfleet had a policy where captains and other commanding officers had discretion over their personal and crew uniforms, departing from a standard. The new "Oddysey" style uniform was adopted for all general staff and those crews who had not opted for a custom uniform
FROM: Fleet Admiral Jorel Quinn
TO: All Starship and Station Commanders
REGARDING STARFLEET UNIFORM CODE
This memorandum is to inform you of updates to the Starfleet Uniform Code Subsection 1 effective Stardate 87003.
As the political realities throughout Federation space continue to shift,
Starfleet must remain a force for consistency and stability. To that end, the
admiralty is enacting a fleet-wide update and standardization of the Starfleet
duty uniform. Starfleet has officially and totally adopted the uniform designated
“Odyssey”, which has already seen initial deployment by personnel on Earth
Spacedock in Sector 001 and in several fleet command starbases across the
The Odyssey uniform design provides a solid link to Starfleet’s heritage while
establishing a bold direction for its future.
Attached to this message are replicator patterns for the Odyssey uniform. We
have authorized all starship and station commanders to begin replication and
distribution of this uniform among their crews effective immediately. Please
also see the attached uniform specifications on appropriate accessories,
coloration and wear.
NOTE: Subsection 2, Paragraph 1 of the Starfleet Uniform Code remains in
effect; Starship captains continue to have discretion as to their personal
uniform and the uniforms of their bridge crew.
Fleet Admiral Jorel Quinn
Starfleet Command, Earth Spacedock
It is possible that this policy existed in a similar fashion back in the DS9 Era, and Sisko was given leeway to select station uniforms to his liking and to fit the needs of the base. In this case, Terok Nor was an inustrial mining platform that had been stripped and sabotaged by the Cardassians. There was a LOT of dirty grubby work to do. To this end he may have selected the workman's jumpsuit style uniform out of prudence to the work needing doing.
When Starfleet released the grey First Contact style uniform later on, Sisko likely decided that the need for the rugged jumpsuit variation had passed, and opted for the more militarized look to meet the needs of the growing conflict with the Dominion.
Other evidence to show this trend was the moderate continued use of the skintight uniform on TNG well into the general use of the Starfleet Duty Uniform used in the latter half of TNG, along with various scientific outposts using slightly modified uniforms through all series. Seen here for training, excursion, flight suit, B'elanna Torres's work jacket, as well as personal modifications such as Worf's Sash, Bajoran Earrings, Maternity alterations, Combat uniforms, MACO gear, etc.