I started with Adventure itself. My second game - and the one that hooked me on IF - was The Plant by Michael J. Roberts. I used walkthroughs for both of them, which probably means they’re not really that good for beginners.
Whenever I recommend IF to someone, I start them on the Earth and Sky trilogy, or Emily Short’s Floatpoint. Blue Lacuna has a good tutorial mode, but the length is intimidating. An Act of Murder is reasonably easy, uses fairly simple commands, and has a good hint system. Those are my picks, anyway.