For the temporary fix I'd recommend making people unable to pick up grenades and instead of adding a grenade on respawn, give it a set time respawn somewhere between 2-3 minutes. As someone already said the grenades themselves are fine, it's just the incredible volume of them that come flying at you in a full game. As far a alternatives:
1. Throwing knives/stars- 5 per spawn. Would take 6 to kill someone from full health on body shots. Head shots do double damage. Say 40% higher air speed than grenades.
2. Mustard Gas- Does say .1 % damage per second someone is in the gas cloud. Gas cloud lasts for 30 seconds.
3. "Sticky" gloves- Lets you climb up any vertical surface and give you limited distance climbing across ceilings. Gives you 40% greater climbing speed. Jump to a wall and hold jump to initiative a "wall slide". Holding back makes you slide down the wall faster (as does firing any one handed weapon). Holding forward makes you slide down slower until you stop (stop distance is increased while firing a one handed weapon) and start climbing up. Using a two handed weapon makes you start falling. While on a wall hitting stunt button does a backflip. Hitting a left, right or back and the stunt button makes you dive off the wall in the given direction. If you are on the ground facing a wall, press against it and hit jump to start climbing up.
Edit: One more idea
4. PCP- For some limited amount of time the benefits are 75% melee damage reduction, immunity to execution, 10% bullet damage reduction, and +2 second of slow-mo for every kill. Disadvantages are no fine aim, +20% reload time, +10% recoil, -10% dive/slide distance.