I certainly can't give you exact dates, or even years, but the ballpark was:
BR Vest and new duty gear was the 97-98 time frame. We had these well before OPD came on the scene in 2002-2003, there are a ton of pics showing Army MP wearing it with combats and CADPAT and Air Force and Navy MP in their base dress of the time. OPD was the direct result of the rainbow effect of a non-standard patrol dress.
Vehicles were not a switch directly from the black, propane powered, Chrysler and Plymouth sedans. There were a few intermediate steps. From what I saw it went:
Black Chryslers to white Ford Taurus SHO: 90-92ish
Ford Taurus to Chevy Impala: 95-97ish
Chevy Impala to Crown Vic: 00-02ish
Those dates are obviously even more widely variable from what I recall due to the fact acquisition of the vehicles was the responsibility of Base Transport at each of the Bases. As a result, some Bases were consistently early adopters of new types, whereas others retained previous models well past the date most other places had transitioned.
There were a variety of non-standard patrol vehicles kicking around in different locations as well as a result of this, probably the most infamous being the "ghost" vehicle in Borden that was grey with low vis MP markings for their "traffic" section because a certain MPO was able to convince Borden's Commander and BTnO that it was a good idea, notwithstanding what MPTTP said.