a few more easy "strategy" games: Lemmings, Kingmaker, Megalomania, Populous

and a couple of old "adventures" by unconventional publishers: Mission Critical, Future Wars

Complex games tend to turn me off as well, like for some reason I like HoMM 1 better than 2, 2 better than 3, and so on. Sometimes the most sophisticated game would sound awesome, then turn out to feel more like work.

Maybe you'll like Mad TV, one of my favorite games of all time. The formula is just..... perfect. :)

http://www.classicdosgames.com/online.html

This is kind of a hard question because when you've played a game for over a decade, it will never feel complex to you.

Having said that, here's some games that are amazing fun to play. Some are a little deeper and take more effort but those are more rewarding as well:

Abuse: a nice and simple action game
Aladdin: a very solid & fun platform game
Alien Carnage: an even more fun platform game
Ascendancy: very fun strategy game
Beneath A Steel Sky: my favorite adventure game and free on GOG
Cannon Fodder 1&2: war action game which is very easy to play but very hard to complete
Command & Conquer 1 + Red Alert: both free games and both great still
Crusader No Regret/Remorse: action games - on GOG
Dark Legions: a very underrated combo of action & strategy
Day of the Tentacle: brilliant adventure game
Duke Nukem 3D: nuff said
Earthworm Jim 1&2: still two of the most original and entertaining platform games
Ecstatica 2: very solid action adventure
Fragile Allegiance: my favorite DOS adventure game
Fury of the Furries: another original platform game - very fast, very fun
Indiana Jones & Fate of Atlantis: brilliant adventure game
Lands of Lore: one of the best square-based first person RPGs you can play
Lemmings + Lemmings 2: true classic strategy games that don't age at all
Micro Machines: very fun game with a friend! Driving tiny cars across tables and stuff
Pizza Tycoon: another favorite strategy game of mine
Prince of Persia: very hard but easy to get the hang of
Sam & Max Hit The Road: brilliant adventure game, very funny
Screamer: solid racing game
The Incredible Machine 2: very smart game where you build machines
etc. etc.

There's really tons of great games - games back then weren't that complex but often had a lot of character and originality - and they could be HARD to complete too but easy to pick up.

How has no one mentioned X-Com?

A bit of a learning curve, but one of the greatest games of all time, and once you figure it out you'll never forget how to play it.

For the multi-player within you, head to dosmp.com.

It works (somewhat) on my Windows 7 64-bit.

I haven't played them since I had a C64 with 5.25" floppy drive but the SSI Gold Box AD&Ds!
Unlike some of the games you mentioned they have a handy automapping feature but they HAVE saved on in game text and graphics by refering you to a journal for journal entries so you'll have to have that pdf on standby
Same deal with 'Wasteland' - the pre-cursor to Fallout, which I haven't played but am meaning to
I also remember the Bard's Tale series being pretty good back on the C64
For something a bit more action orientated LBA (Little Big Adventure) and Flashback have popped into my head

I never really played DOS growing up, I guess now's as good a time as any:

Where do I begin?

Crusader: No Remorse and No Regret are simply awesome. I'm rocking them both on my own GMA 950 MacBook and they run great in Boxer.

For good platforming action, Rayman Forever and Earthworm Jim 1/2 are excellent, while Gabriel Knight: Sins of the Fathers is an excellent point-and-click adventure game (perfect for a late rainy night). I'll second and third the recommendations for HOMM 1/2 and MoO 1/2; for a good strategy/4X game Conquest of the New World is a great game too.

Of the bunch though, I have a special place in my heart for Master of Magic - I think I lost a few months of my life to this game after I bought it on GOG.

I can't read the interface or understand the game screen when it gets busy. :(

Carmageddon.

Probably my favorite racing game evar. I recently bought sealed Carmageddon big box at ebay, so exciting. Maybe it's the last sealed Carmageddon box in the world LOL I don't even know if I'll be opening it, it'd be like killing a unicorn.

Already mentioned Prince of Persia 1 and 2.
Two other great platform/action -thingies Another World and Flashback.

RPG + Strategy elements aplenty in one of my all-time favourites: Syndicate.
There's also a dos version of the almighty Fallout.

Settlers 2
/thread

Mad TV is also one of my favourite games ever, though I lost my copy years ago. There's a pretty decent browser based version I've been playing though.

Good pick!
There was a demo included in Boxer, but like you said there's a learning curve so I couldn't play for too long. I'm thinking next time this goes for cheap on Steam I'll grab the data files.
I've heard many things, all of them good. It's now wishlisted. Thanks!
Thanks a lot for the great list. I've played a few on there, but I'll try to get a hold of the others.
Great suggestions. I've been saving Master of Magic for when I'm tired of Master of Orion 2, but the fact that it's come up four times now is promising. And I've never heard of Conquest of the New World, but I'm definitely looking it up.