Story?- I want an involving experience
Naturally, you want an original and coherent plot to follow, right? You don't want to just be dropped in a room, given a crowbar and a horde of zombies and be simply told to 'Have at it!' Even if the overall setting is the same and you are dropped into Black Mesa or some district of City 17, you want to be guided to some degree, and to meet new and interesting characters.
Visuals?- Eye candy or GTFO
You certainly want it to look good. Anything that is orange mapped or put together in MS Paint simply won't do, am I right? If the developer hasn't taken the time to put in the time and effort, why should you bother even taking it seriously? It needs to look good and the setting should well realised.
Something new- I don't want to play Half-Life again!
It needs to be new. You don't want to shoot headcrabs anymore! You know their attack patterns off by heart and could dispatch them in your sleep. It simply isn't challenging anymore. You demand something fresh! In fact, maybe you don't want to shoot anything! You want a puzzle platformer that will challenge you in an entirely different way!
Something else?- Urby! You didn't mention mash up mods! I love mashup mods and I am also a moron who deserves to get some kind of disease that only really stupid people get!
Maybe you look to get something else entirely, that I haven't suggested. Pitch in! Let's hear it.
- - -
Of course, a combination of all the above would be nice, but is rare. If I had to chose the most important aspect, I would say visuals. I can forgive a total lack of plot and an overall objective if I get something pretty to look at. Story is certainly a close second for me though.
As for completely new experiences, meh. I could quite happily run through a thousand different peoples take on Black Mesa, or even if the environment is completely different I would be totally cool with Half-Life's FPS mechanics as standard.