You're probably not doing anything wrong if your colour is matching across colour-aware applications.
Photoshop should be set up like this:
(note: I'm using CS2, but it should be roughly the same)
And Lightroom's settings should be like this:
What you are seeing is probably the difference between your monitor and the sRGB spec. With my laptop LCD where the gamut is much smaller than the sRGB colour space images look very pale/washed out when there is no colour management in effect. I imagine that viewing images on a display where the gamut exceeds the sRGB spec will look oversaturated in unmanaged applications.
It's just a case of having to trust that the image
will look as it is meant to on more accurate displays.
Safari (and Internet Explorer, I believe) has had colour management on OSX for many years now, so as long as your images are tagged with a profile they will look correct for anyone viewing in it.
Fortunately, there are now two browsers for Windows that are colour managed - the
Safari Beta, which should do a reasonable job, and the
Firefox 3 beta.
In Firefox colour management is disabled by default, but you can enable it by typing
about:config in the address bar. Now, in the filter section, type in
management. Double-click
gfx.color_management.enabled to change it to true, close all browser windows and re-open it, and it should be working. The great thing about Firefox is that it automatically assumes everything is sRGB if it is untagged, so everything is colour managed. (I suppose there are cases where this could cause problems, but generally anything on the internet is supposed to be sRGB)