When a grenade explodes in water, the shockwave does more damage to a human than when the same grenade explodes in air. I am aware that the incompressibility of water as compared to air plays a large role in this. However, there's also definitely a pressure difference between the two substances. Based on that premise, I think the same explosive would be even less effective in air that has less pressure than Earth's. Would this be the case?
Yes, the density of the material in which the explosion occurs matters. The damage done by an explosive comes from: shrapnel caused by debris, heat released and the shockwave released. An explosion is basically a solid/liquid being converted to a gas in a fraction of a second which then expands.
In water, the gas displaces water which sends a shockwave through the body of liquid. When creating an underwater shockwave, water is is a bad compressor which means that the shockwave vanishes after less time. It might be more deadly at close range but the shockwave doesn't spread as far as it would in air.
In a low density atmosphere, the opposite properties would probably be observed. Unless you were standing next to the explosive (where the gasses releases would be dense and the cause of the shockwave) there wouldn't be as much danger. The shockwave would travel much further and for longer but the strength would diminish rather quickly
In direct regards to your question, the density of the medium does play a role in pressure. $$ P = \rho. R.T $$ Where P is pressure, rho is density, R is the gas constant and T is the temperature. This is for gases only but you can see that in a less dense atmosphere the pressure would be less.
To sum up, yes, a less dense medium would not carry the explosive shockwave and the winds would not be able to do damage
Fragmentation grenades are normally designed to produce a large number of very nasty deliberately designed fragments that rip people apart very well. Low atmospheric pressure will reduce the shock wave, but those fragments will still rip into people. I would consider the word "grenade" without qualification to mean a fragmentation grenade (a device designed to kill and maim infantry by fragment).
There are other types of grenade which are based on the shock effect, and this will be lessened if the air density is low, but note that where you set off the weapon is important. Shockwaves bounce around and a relatively small shockwave in a confined space can be devastating, while outside it does almost no damage. Note that stun grenades are generally also designed to incapacitate with light (temporarily blind you) and that doesn't change.
Low air density may also translate into a longer range for those fragments, which is not so good.
Now if a shockwave is reduced in intensity that doesn't mean it doesn't still have enough power to e.g. stun or knock over someone. In terms of damage in a battle scenario, survival is good, but if you're temporarily incapacitated it can be just as lethal in the end. This might be relevant to your scenario.
So if you're talking about fragmentation grenades I'd not expect much joy from a low atmospheric pressure, as the fragments are still going to do major damage.