PC games in general: should have 256 VGA (or exceptionally good looking EGA) graphics and sound card support (forgiving that to some newer indie games and hack clones where e.g. ASCII "graphics" and no sounds was a design decision). For games beyond that, I'd rather look for Amiga, or even Commodore 64, versions of the same games.
Also, a game tutorial (missions) is much preferred for games with a steep learning curve, over having to learn the game from a manual. E.g. flight sims, mech games etc.
FPS: like someone else said, has to have mouselook. Doom and such is too oldskool for me nowadays, Duke3D like games like Blood 1, Shadow Warrior etc., I'm still willing to give a chance, even though their mouselook is rather wonky. I know original Doom also had some kind of mouse support, but IMHO it didn't work that well, and it wasn't actual mouselook anyway, just turning with the mouse.
CRPGs: as said already, need automap and quest log. Not much else, I consider ADOM a passable CRPG even today, even if it is a hack-clone with no story etc. For early 80s, I probably prefer even console JPRGs on NES (early Final Fantasies etc.) due to better playability.
Action games: no "three lives and you are out" type or coin-op ports anymore, it has to have some kind of savegame system.
Adventure games: anything with a point&click interface or newer... except that for some odd reason I've started to think about trying some old text-based adventures, e.g. from Magnetic Scrolls. Maybe my English is currently good enough level for them, and I don't have to stare at a dictionary all the time anymore. Back then it just felt I used most playing time trying to come up with the right verbs to be used in text adventures.
Strategy/RTS games: a bit harder to describe, but if the user interface is just too restricted to be enjoyed anymore, it's out. I did replay Warcraft 1 and Dune 2 recently, but frankly I disliked the UI now. Maybe as you said, from C&C, or Warcraft 2 BNE, onwards is fine with me.