The G-Man's name is a reference to the fact he looks like a standard midlevel government employee, with his uptight suit and briefcase. Corporal Shepard even refers to him as a "G-Man" in his journal (Opposing Force user manual).
The G-Man is, I believe, an intergalactic "Fixer". For whatever reason, the various powers in the interdimensional universe cannot interfere directly. The G-Man saw an opportunity in Gordon, who by some means survived Black Mesa - an incident the G-Man likly arranged at the behest of the Nilhinath so that it could attempt to escape the Combine. The G-Man however is not all powerful- he seems to be able to move out of synch with time, and through space. But he was blocked by the Vortigaunts in Episode 1, suggesting that the gestalt power of the Vortigaunt race is equal to or greater then his. He also seems unable to interfere except on a very limited basis. The G man likly represents some powerful, mind bending form of life that early man would've confused with angels and demons... infact, some sort of demon is the best way I could describe G-Man. He's an influence broker, but he can't directly intervene.
The plot of Halflife is a bit hard to follow because it's not clearly explained in the games- one of my few griefs with it- but the bigbad of Halflife was the Nihilinath, the giant baby thingy. It was formerly a part of the Combine, or threatened by the Combine, and stole a great deal of slaves (such as the Vortigaunts) and fled with them. In order to escape the combine, it siezed on the breach created by the resonance Cascade, until Gorden slew the Nihilinath. The Combine glimpsed earth during this period and followed some years later into our dimension, resulting in the 24 hour war where earth was Pwnt. Dr. Breen, who had become Secretary of Extra Terrestrial Affairs in the ensuing time due to his experiance at Black Mesa, surrendered Earth to the Combine to prevent immediate extinction.
A thought occured to me though, that the people employing Gordon Freeman through the G-Man might be the Vortigaunts themselves. The reference to "Their only experiance with mankind at the time being someone running down the hall towards them with a crowbar" quote makes me think of them. Their conflict with the G-Man in Episode 1 maybe a result of them desiring to prevent him from selling Gordons services off to another bidder, or keeping him for themselves for longer then was agreed upon. The Vortigaunts have been enslaved by the Nihilnath and the Combine for millenia supposedly, and Gordon is their ticket to freedom. You gotta listen to the Vortigaunt at the start of Route Kanal talk for a while to get everything, and it's somewhat cryptic- but 'The Freeman' free'd them from slavery to the Nihilinath, and now the Combine is killing them on sight because they can't be directly controlled anymore.