I would play them all in order of release. Don't listen to people bang on about Invisible War, it is still a good game IMO, just not as good as the first one.
Story is a very important part of Deus Ex. If you cannot stand the graphics you will be losing out. If this is the case I say try HR and then MD.
Would be a bad idea to go straight to MD, as while it has the best graphics, in my opinion it has the worst story of the lot, not that it is bad or anything, just does not live up to the quality of the rest.