I think Gothic is a terrible idea for someone new to old games. It plays like a clockwork turd. I don't even know what that means, but sounds about right. Ig grew up playing old games back when they were new, and now often play for the first time some very old games that I didn't get to play back then for some reason, and still I could never get into Gothic.
Some ideas of mine:
RPG
Knights of the Old Republic- if you like Star Wars and are looking for a good story, it doesn't get better than this.
Legend of Grimrock- not really on old game, but a perfect way to get into old-school RPGs. It looks good and is easy
to pick up for new players, but it plays like classic duneon crawlers.
Fallout- despite it's age it's still a great game, and it's much more accesable I think than the D&D based classics like Baldur's Gate and Torment. Great world, good story, it's worth sining your teeth into.
Strategy
Heores of Might and Magic and Disciples series- if you have any interest at all in turn based strategies (mixed with RPG elements) then those are the absolute best games you could find.
FPS
TRON 2.0- probably the best and most unique first person shooter ever. Graphics still hold up, the level design is great, asis the entire world and story, and gameplay is just perfection.
Medal of Honor- a true classic and for a reason. It aged very well for the most part, and the Battlechest edition on GOG is truly a treasure trove of content, with expansion packs I think even better than the base game.
EDIT: Oh, and I have no idea if you have any interest in adventure games, but the Monkey Island games are a gem that everyone looking into classic games should know, and the new Special Editions make them very friendly to new players, with full voice acting, better interface and a hint system to help out in case the more insane puzzles give you a hard time.