I played Half Life 1 first, thought it was playable (I couldn't shake the feeling I was playing a glorified Counterstrike mod, was still a solid game though) and later went on to play Half Life 2 (upon a friend's reccomndation, namely because he needed me to write a review for it for his site).
The story IS connected between the two in the same sense that the plot of AVP 1 and AVP 2 are connected, they are technically connected but only in a vague way (Half Life 1, as far as I could tell, didn't have much of a story besides 'get the hell out of dodge because aliens have appeared and the Army is really pissed off').