My first recollection of having a "conversation" on a computer was ~1984. It was a text-based game on the Apple II that I can't remember the name of, but at some point in the game you could end up in a church or temple, and you could ask it anything. Of course, the game was limited in the number of different answers it could give at random, but the answers were all general and sagacious enough that they could be interpreted as some kind of meaningful response (at least to a 12 y/o). Wish I could recall the name of the game. Anyone?
Several people have suggested Zork. I don't think that's it. It was a text-based game, but believe at the point in the game I'm talking about there was a simple black and white cross showing while you were talking to the supreme being or whatever.

@briankrebs so many games from that area were totally lost, particularly in the realm of interactive fiction.

But I have a pretty vivid memory of that being from Mystery House, which was a semi-graphical game.