hydrogen sulfide is more nucleophilic than water. The rationale that I have for this statement is that S is larger than oxygen, so its valence electrons are held more loosely, therefore they could be more easily donated than those in the valence shell of oxygen.
Also, the sulfur would not have to get as close to the electrophile to form a bond as the oxygen would.
Also, statement one in your last post is true, to the extent that water is a stronger base than hydrogen sulfide, I believe. -OH is a stronger base than -SH, so that fits with this theory.
As to your original question as to why this reactions goes SN2 and how, methyl iodide, for example, is a very toxic compound, simply because it methylates anything in sight in the body. The things methylated here would be things like alcohols, amines, thiols, etc, most of which would likely be protonated when they act as nucleophiles, but the reaction still occurs readily because the carbon iodine bond is so weak, so MeI is a good electrophile (similar to MeBr).