Asking whether Half-Life or Halo is better is like asking whether Starcraft or Warcraft 3 is better. They are both so great, it is hard to decide!
I personally prefer Halo because it is more combat-oriented... there is never a moment where you are stuck wondering, "What boxes or buttons do I have to push to get over there?"; the game is grenade-throwing alien-slaughter from start to finish. I've never been a fan of puzzles in First Person Shooters, but if there's one compliment I can give it's that the button-pressing and box-stacking puzzles in Half-Life were MUCH less odious than most other games. (Trespasser and Jedi Knight 2, anyone?)
Half-Life's level design was MUCH better than Halo (with the exception of the end levels); I don't think any other game has come close to the quality of HL's levels. Max Payne had several exceptionally good singleplayer levels, but they were very short, HL's levels were huge.
HL's difficulty levels really weren't much of a difference compared to Halo's - hard vs easy you dealt half as much damage and took twice as much, while you take >10 times as much damage from Legendary difficulty compared to Easy. (partly because Halo's Easy difficulty is so retarded, you could sit in place and watch your shields regen faster than enemies can hurt them) However, the smaller spread in difficulty levels in HL meant that AI allies were balanced on all difficulties, while Halo's marines will do all the work for you on Easy or Normal, but on Legendary they die in seconds.
Although HL and Halo belong to two different generations, they are similar in their accomplishments. Half-Life took the "shoot tons of aliens" FPS genre established by DOOM to a new level, adding an immersive plot line, intelligent scripted and unscripted AI, and top-notch level and enemy design. On the other hand, Halo took the genre established by Half-Life and dumped in loads of "cool factor"; the Covenant, Sentinels, Flood, and general weapons + vehicle design are all very very cool and just fun to play.