If you want to start with an Infocom game, I found "Nord and Bert Couldn't Make Head or Tail of It" to be a fun little amuse-bouche. It's a wordplay game instead of a lengthy story full of old-style adventure logic, so you really can't get "stuck", and is also an interesting example of a game that fundamentally could never be anything but a text adventure.

(This may depend on your wordplay ability. A quick check on Wikipedia says fan consensus on the difficulty ranges from "Standard" to "Expert". Oh well. It's 2015. You're only about 30 seconds away from a walkthrough. Given the nature of the game, it won't ruin anything if you have to consult a walkthrough once or twice. In the meantime, it's the only Infocom I've ever beaten without a walkthrough at all. My brain seems to really, really not jive with text-adventure game logic.)

Granted, it's very different than a text "adventure", but I think if you've never played a pure text-based game, it's a very gentle and genuinely entertaining experience.