I would say that I really liked Star Trek: 25th Anniversary. It is an adventure game for DOS, and you basically play out a set of scenarios with Captain Kirk's crew. The objective of the six or so scenario varies, but the theme is just like the show: Try to find the best solution. This means being diplomatic, not using phasers on kill, so on and so forth. It really captures the show perfectly, as does Judgement Rites. However, you are also free to be an inept Captain Kirk, you just lose points for not following the preferred route. So you can make quite a few mistakes and still get to the end.
Moving onto platforming glory, I heartily nominate La-Mulana. 8-bit graphics that are succulent to behold, MetroidVania gameplay with a serious dash of Zelda...and it is free. A really good combination, I say. If MetroidVania isn't your bag though, give Gun Hazard a shot. Featuring a rather heavy story in the Front Mission world, you play with a mecha in a side-scrolling RPG game. Looks good, quite serious, and just plain neat.