It doesn't necessarily have to stain bridge substructure. There is a report available from the Texas Department of Transportation on proper detailing of weathering steel girders to avoid stains (it basically comes down to directing rainwater away from the column surfaces). Contact the Construction Division, Materials & Pavements Section. I don't know if there are ways to detail a weathering steel building to protect surrounding pavement.
Definitely not good when exposed to salt or frequent wetting; you wouldn't want it on a low bridge over a stream.
I've heard that local air quality plays a large part in what color it'll turn--chocolate brown, purplish, orangish. Make sure you blast all the mill scale off visible surfaces or it will look like crap for decades.
There's a slight cost premium on weathering steel plate, but it's generally considered to be made up for in painting costs, especially when you take in lifetime costs--a painted bridge will need repainting every 10-20 years.
Hg