As for my recommendations I don't have much, however I will second Battle for Wesnoth, a simple yet fun (and not quite HoMM-like) strategy game. Had lots of fun with it, even played on their multiplayer server a while back. (I don't anymore, because I'm not real good at the game :/ )

That aside, I personally think Heroes of Might and Magic 3 is one of the best TBS games ever devised. (/my opinion)

no... the Licurg dolls did not go well did they?! ;D

Yeah but Batttle for Wesnoth is basically like Fantasy General/Fantasy Wars, so might be too much meandering^^

King's Bounty pre-dates HoMM; the later is something like a "spiritual successor", to use an extremely popular marketing phrase.
It was also not the version we have on GoG, obviously. http://i1.ytimg.com/vi/DQ0U9ZXGiig/hqdefault.jpg

I replayed the classic Battle Isle on PC with keyboard several times, it's not too hard to get used to.

I like that the first Battle Isle has relatively small independent maps which can be played quickly.
BI2 and BI3 already are too big for my taste. Didn't play Incubation yet.

Agreed, kmonster, they are ok with the keyboard, the mouse is too wonky,though. I prefer History Line, recently played through both campaigns again, it aged pretty well!

Look to the consoles and handhelds, they have strategy games that are very different from what you would find on the PC. Things like Ogre Tactics, Advance Wars, Growlanser, Disgaea, and so forth.

Lords of the Realms 2 - medieval TBS, and very playable. The graphics in battle mode are blocky, but very clear. The enemy NPCs have entertaining personalities which influence their battle strategies and how they abuse their territories. The parts of the game work well together. It's got surprising depth, but it's not the most hardcore tactical game.

Alpha Centauri - if you like science fiction, this is one of the best TBS of the past 2 decades. It's really, really good. I keep going back and being surprised by how much I like it. The whole game works well together - there's no part I can especially call out, because it's all done well. Maybe the secret project research intros - those are very, very well done.

Something like Stronghold maybe?
Edit: Whoops! Missed the TB qualifier there. Hmmm. Hmmmmmm. I'll have to get back to you one that.

If you liked Advance Wars then what you are looking for is the Battle Isle Series, after all the Advance Wars Series was heavily inspired by Battle Isle. You can get most of the series with one purchase: Battle Isle Platinum.

If you happen to like that there is also one more part in the series (Battle Isle: The Andosia War) even though most people don't like this one as much as the older ones and the spiritual successor Battle Worlds: Kronos.

Aye - have BW:K already (meant to mention earlier in the thread).

I'd still advise you to get the Platinum collection if you don't have that yet. That many great games for one small price is unarguable the best bang for the buck you can get on GOG. Incubation alone is worth the price. Great game. Even though my personal favorites of these would probably be BI2 and 3, which I like even more.

have added to wishlist and will investigate further - cheers!

Wasn't Fallout Tactics in real time? Or does it have an option to be played turn based too?

It has both real time and turn based options.