The Call of Duty: Modern Warfare series did a good job of balancing most of their weapons, so most people thought that their preferred weapon loadout was the best.
If they can convince millions of people that their favorite weapon is the best, with them all choosing different weapons, they did something right. I strongly suggest playing one of them if you haven't before - they did alot right when it comes to persistent player level-ups without unbalancing things. Not perfectly balanced, but very very close, while still feeling meaningful.
(I'm talking about Modern Warfare 1,2 & 3. The Black Ops series is made by a different developer and doesn't quite have the same level of polish, IMO)
Despite my above praise for the series, I'm actually not a heavy FPS player, and only have dabbled at Modern Warfare here and there - but I was really impressed with the single player and the multiplayer portions of Modern Warfare. Kudos for the Infinity Ward developers - they did an amazing job, and this from someone who barely plays the genre (but I have experienced enough of the genre in other games to know quality when I see it).
"Leveling up" should unlock new tools for overcoming challenges, without making any existing challenges easier.
The new tools really do need to be different. Not the same thing with a different visual appearance.
A sniper rifle and a shotgun are two different tools with different uses in different situations.
What if, for each level up, you are presented with five different pieces of equipment, and you get to choose two of them to unlock and add to your possible choices.
When you begin a match, you choose which three pieces of equipment of your unlocked equipment you want to actually bring into battle.
You can replace the word "equipment" with "skills", "items", "abilities", "magic", or whatever - the concept is still the same.
The important thing is that new tools you unlock don't make old tools obsolete. Getting a sniper rifle doesn't make a shotgun obsolete, or vise-versa.
What if one piece of equipment is boots that let you double-jump? It doesn't make you more powerful than other players, but it does make you more maneuverable.
Someone else, for their boots, is wearing one that lets them constantly run slightly faster (25% faster, let's say), and another person is wearing boots that let them run alot faster (100% faster) but only for 5 seconds at a time (requiring them to use it cleverly, and to make them _work_ to have it be a real advantage).
The best thing you can do is to introduce meaningful choices (choices that actually affect the gameplay) to the game, without overwhelming the players with too many options presented at once.
The worst thing you can do is add additional items to the game that become the obvious choice, because they are unbalanced. This removes choices from players.
Other areas where there might be a couple different choices:
If you have explosives in your game, you could have: Timed explosives (you throw them and they detonate after a set time - i.e. grenades), proximity-mines/claymores that are triggered when players walk near but make a 'click' noise when triggered and have a two second delay, or remote mines that players manually detonate but that detonate instantly when the player triggers it.
Other familiar explosives are smoke grenades and flashbangs. What about poisonous gas grenades? Or what about noise grenades that sound like someone firing an automatic weapon, and show up on the radar as a player? What about hallucinogenic gas grenades that make a knee-high colored gas that spreads from room to room and flows over ledges and distorts the screen of people that are inside it?