I unfortunately have little to add to Bumvelcrow and Strange Fellow's recommendations, they've both mentioned all the highlights. I'll reiterate some of their advice and try to add some of my own.
My personal favourite is Trinity, way up there. I don't know if it's the best one puzzle-wise, but its puzzles are excellent regardless, and it is one of the best (if not THE best, and I don't use this kind of ranking lightly usually) written games ever. Leather Goddesses of Phobos and Spellbreaker are two other fantastic ones (though Spellbreaker is the third in a trilogy, and the first two (Enchanter and Sorcerer) are worth playing). Hitchhiker's Guide to the Galaxy is worth it if you like the books/radio series. The Zork trilogy are classics, not exactly easy but not among the hardest either.
None of these are easy games and I wouldn't consider any of them a good introduction to IF. As Bumvel mentioned, Wishbringer is a good introduction and quite easy. A Mind Forever Voyaging is also very easy, and one of Meretzky's most original cretions. There's also Plundered Hearts, not the best but a good ease-into.
The one Infocom game I'd say to stay away from is Infidel. Some of the others are odd but interesting experiments (Nord and Bert Couldn't Make Head or Tail of It), though some of these can also be very tough and not always fair (Bureaucracy).
Legend games tend to be a good introduction to IF, as they're easier than Infocom's. Eric The Unready in particular is really good, very funny, and the parser is EXTREMELY flexible and will respond to pretty much anything you can think of. Timequest and Gateway are also excellent (Gateway II not as much). Spellcasting 101 is quite good, it's a Meretzky-naughty version of Enchanter (though both sequels are very inferior).
There were a lot of good independant IFs released in the 90s and early 2000s. Andrew Plotkin was a good one, hist most famous is Spider & Web. I forgot the name of the author, but there's one called Perdition's Flame that is now free I think and that's not a bad introduction (no death, no dead ends, puzzles are not easy but very fair). Going into more difficult territory, one of my favourites is t-zero, which is what playing a James Joyce IF would feel like (it's a VERY hard game too). On the easy side, Adam Cadre has made some very simple ones that are extremely well-written, namely Photopia and Shrapnel, and a "real" IF game that's also very good, Varicella.
This should keep you busy for a while