Alleycat: Very challenging classic game and very fun. You play as a cat, trying to do several things, by trying to break into people's homes. If you don't like it, then at least listen to the music at the title screen, it rocks.
Battle chess: Simple concept: chess with living pieces. Execution is great because it is very satisfying seeing your opponents pieces being smashed.
Prince of persia and prince of persia 2 shadow and flame: Another classic that's also hard as nails. You have a time limit (60 minutes IIRC) in which you have to save the princess. You can die as much as you want, but once you run out of time it's game over. After completing this game, you will hate spikes with a passion, be warned.
I didn't really play much DOS game, but these are the ones I liked. Graphics are very old though, most games are from the early ms-dos years (with the exception of PoP2).