You don't really miss much of the story if you start with Half-Life 2. You might not understand couple of references, but it's a good game to start with. I didn't really like Half-Life a lot, it's a little difficult but that's just how games were when it came out. EP1 was a disappointment, it was short and you pretty much do all the same things you do in HL2. EP2 is just awesome, it takes place in the countryside which is some nice variation from all the city fighting in HL2.
But overall I would just recommend you start with HL2.