Never heard of Unreal Tournament or Quake III Arena, aye? Weapon balance was figured out years before Halo. You still can't find a finer example of deathmatch than Quake III Arena to this day.
If you only want to play online because they were both mutliplayer/bot only games. I was extremely disappointed in Tournament and barely played Arena since I always saw them as half games. I seem to remember the rocket launcher basically dominating most of the time though (maybe it was because my friend always played rocket arena) and I think the starting weapons were both pretty pathetic compared to anything else.
Also there was weapon balance in single player Halo as well while these games lacked a real single player campaign entirely.
Take a look at Quake, Quake 2, Doom, etc. All offered their full singleplayer campaign as co-op, starting all the way back in 1993. Admitedly, this wasn't done in a split-screen fashion... but really, who wants to play any game in split-screen?
Everyone does, look at the Wii's biggest successes today which happen to be some of the biggest successes ever. Broadband around the time of the those games wasn't exactly readily available either and online was the only coop. Remember Halo 1 had no online outside of gamespy tunnel.
Halo was also designed around coop. The most used vehicle in the game needed a second person to be effective and having a partner meant more than just two people charging into a room shooting. Desiging a game with a concept in mind is very different then throwing a second person in Doom. Vehicles, while a few games had them before Halo was released, were still a new thing for FPS games. When Halo was first shown the vehicles blew people away and even though other devs released earlier they were still fresh.
Halo combined all those different things into a single package, as well as other parts that you don't like but remain popular.
I have no problem with regenerating health either Broodwars. They allow for much bigger battles and don't punish you too much for making a small mistake. I remember when I played Half Life I was low on health one time and I basically had to quick save after every guy I killed because the next guy would kill me in one hit. In regenerating health battles they can always go all out on you because they can always assume you have 100% health which makes a lot of the fights more dangerous than they usually would be. I wish every game didn't use it but I enjoy it.