I left my stainless steel frying pan on the hob empty for a while by mistake. It got very hot indeed, I ran it carefully under the tap to cool it down, which took a while - lots of steam. Now, there's a kind of black residue inside, that wasn't there before (it was clean while it was on the hob). I can't remove it even with the toughest of detergents and pan scourers, is it safe to cook with this pan any more?
What you are seeing is almost certainly a form of firescale, and it should be completely harmless. If the discoloration bothers you, you can try to remove it using the aforementioned Barkeeper's friend or a mixture of boric acid and denatured alcohol (which are non-toxic).
With regard to cooling off the pan, you should never put a hot, empty pan into a cold, wet sink: The temperature change can cause the pan to warp.
Stainless steel pans tend to get brown/black around where the flames are if you heat them empty. I wouldn't worry about it and you should be able to scrub it off eventually.