There is a special interpreter for "Adventure-like" games (Zork!), and apparently at least one has ported that code to an Arduino. You'll need an SD card to hold the game descriptor files, where are (as pointed out by others) larger than the Arduino memory.
That particular version outputs to a TV, but it shouldn't be hard to modify it (or find another version) for TTY output.
Now, a normal AVR can not run as slow as 110bps on its hardware serial port. (I can't tell about SoftwareSerial (sigh))
It would not be awful to create some form of SoftwareSerial that COULD support 110bps, or you could slow the clock down to 4Mhz, which would allow hardware serial to do 110. Neither is "basic Arduino Programming", though.