Strong hold is kind of meh compared with crusader.

Warcraft III is good, but you'd probably be better off starting with Warcraft or Warcraft II.

Personally I'd recommend getting an RTS that does the following things:
- Lets you pause the action at any time and issue new orders while paused.
- Relatively simple economy, research and unit types.
- Follows the basic principals of RTS, making other titles easier to pick up when you branch out.

Games I'd recommend based on this:
Dawn of War - there's also Dawn of War 2 which, in some ways, is simpler. But it's not an RTS nor TBS so I can't really recommend it here, even though in general I do.

Supreme Commander 2 - A lot simpler than Supreme Commander and Total Annihilation that preceded it. That said, Total Annihilation is still a brilliant game and if you're looking for a GOG RTS then that one should be an absolute must have. Even if it takes you a little while to really get to grips with it.

RTS go with Rise of Nations I know people will say Star Craft but IMHO Rise of Nations is the better RTS.

For a beginner for RTS, I'd also consider games which let you freely speed up and slow down the gameplay, down to crawling speed. Good RTS games in this sense are e.g. Starcraft, Warcraft 2, Dune 2000... Just press + and - repeatedly during the gameplay if you ever feel the game is going too fast or too slow.

For some other RTS games I feel even the lowest speed is sometimes quite too speedy, or then it is not so easy to change the speed during gameplay. E.g. Warcraft 3 in the slowest speed still felt unnecessarily fast in some levels (mainly the last mission actually), and I think some Age of Empires games had similar tendency. I guess those games consider it sort of cheating if you slow the game down so much that you have time to micromanage all your units easily.

Obviously turn-based games don't have the same problem.

For turn-based, I'd agree that you should start with some HoMM-game, either 2 or 3. The second is a bit more simple (and, in my opinion, has more beautiful city screens and creature design), but the third has a better campaign. But both are quite accessible. The Heroes-games focus very much on combat and you don't have much micro-management to do (you don't have to manage food production and stuff like that).

If you want to get into some games that focus more on building up an empire, I think Civilization 5 is a good place to start, but still, Heroes 2/3 is easier.

As for RTS, I don't really know a lot. I certainly enjoyed Warcraft 3 very much. The fact that you don't have as many units as in other games actually makes it a good starting point, I think. And it has the best story I've seen in a strategy game.

I don't think it matters THAT much, at least as far as Warcraft III is concerned. The RPG elements are quite minimalistic. You have heroes which are stronger than normal units. Each hero has 4 skills that can be increased on level up. Nothing fancy. Also, in the campaign, each mission has a level cap for your heroes, so you can't "cheat" by excessive leveling.

Thanks very much to all who took the time to reply with thoughtful suggestions for me. I appreciate it very much. GoG has such a great community of old school gamers!

I've decided to go with Warcraft III for my first RTS game. I play WoW very casually and enjoy it and its world. I think I'd get a kick out of learning the backstory playing Warcraft III and the smaller number of units to manage initially sounds good to me along with good story.

For TBS, I am going to start with the Heroes of Might and Magic series but I do plan to begin with the first one. If I don't like it for some reason, I'll move on to the second but I'd really like to try them in order of their release unless someone comes back here and convinces me that the first one is just terrible for some reason but I am thinking that won't happen. lol

I've got quite a few well known titles for strategy games on my wishlists both on GoG and on Steam. I'm looking forward to a completely new kind of gameplay. It should be a lot of fun. I have tried some demos such as Red Alert 3, Shogun 2, Civ V or maybe it was IV, I forget now, a couple of the Warhammer 40k games and I liked them all. I tried the Starcraft 2 demo as well and that was fun.

As if my backlog of games to play wasn't already more than large enough I am going to snatch up a lot of great stuff during the holiday sales and have lots of fun games to play this coming year.

Thanks again all! Happy Holidays and I hope you have lots of fun gaming yourselves!

I almost forgot to mention that I did try installing the free Red Alert 2 game somebody mentioned above but unfortunately it would not install on my Windows 7 64 bit PC. But I did want to mention I tried to follow through on that suggestion. Where I liked the Red Alert 3 demo that's on the Steam wishlist for later.