See Crysis tells the story of Nomad and how he finds out the real truth of that island. Crysis Warhead is a parallel story of Psycho (Nomads squad member) and his adventure in another half of the island after the squad gets seperated. Gameplay wise both are pretty much similar although the original Crysis has more variety in levels (I'd spoil it for you if I told you more) in comparison to Warhead and Warhead is also a lot more shorter. Although Psycho is a lot more interesting that Nomad.
IMO play the original Crysis and -if you want to- play Crysis Warhead after that.
Crysis might be several years old but you would still need a graphic to play it well enough to enjoy the visuals. Crysis Warhead is slightly lighter on system load while maintaining the visuals of the old Crysis.
Yea, play Crysis first. Warhead is optional. Also, both of them are now available super cheap. Although, i didn't understand the logic of pricing the Maximum Edition more than both the games.:S
Actually, the games are slightly different. Crysis is a bit more like Far Cry 2 (if you have played that) where you can sneak around a lot and it is very open. Warhead is a bit more focused and linear. (It's not Uncharted / CoD linear though)