X-com. Either the old ones or new ones work, or similar to it, Xenonauts.
Massive Chalice or Invisible. Inc.
Age of Wonders 3 or my favorite one, The Banner Saga.

I am playing the first King Bounty, however a lot of it's level up stats, army availability, item distribution is very random that I keep recreating the character. At one point I just use cheat and level up the char to 31 to see what level up bonus he have before deciding to use that save.

Are the subsequent KB series very random too?

Try out XCOM Enemy Unknown, you'll love it.

+1 for Battle for Wesnoth.

You could also try one of the Civilization games. I like 4 the best.

By "first King's Bounty", do you mean the original game from 1990, or King's Bounty: The Legend?

I have never played the former, but have played the latter three times from start to finish (once on Normal difficulty, twice Impossible).

Assuming you mean The Legend, then, while there is some randomisation in what you get as options on level up and a few of the armies you can recruit in some places, its overall effect is quite minimal. AFAIK, no matter what you get, you can complete the game. I wouldn't worry too much about it. I have never had to recreate a character.

This does not mean you don't have to choose wisely your level up bonuses, it just means that what you'll get to choose from will be more than enough. It's a very well balanced game.

Eador: Genesis is very well-regarded among those who like games like HoM&M 3. If you prefer 3D graphics, here's also the remake, Eador: Masters of the Broken World, but it initially had some problems, and I haven't heard how well they wound up being addressed. (I've never played MotBW, and I never finished the opening (tutorial) section in Genesis, so I'm hardly an authority. ;) )

I think you'd really like Desktop Dungeons. Didn't have opportunity to check full version, but when it was in an early development phase, it was a great game for thinking about decisions and strategies. Really nice and refreshing!

Yes it is The Legend. I have this OCD to max min everything, so the randomness is eating at me.
I assume the subsequent series is the same?

Sorry. Forgot to answer. Yes, it's the same.

Desktop Dungeons is more of a puzzle game than anything else.

Personal recommendations (i.e. the "if you haven't played this you're no fan of the genre" list):

OpenXCom - play the original on a modern system with all the fancy improvements. Original X-COM (aka UFO: Enemy Unknown) and Jagged Alliance 2 (with the Bear's Pit-hosted 1.13 fan-made patch) are the best damn turn-based tacticals I've played... and I have played quite a few of them.

Fallout 1/Fallout 2. Get it. Play it. Love it.

Realms of Arkania. Great RPGs, still love the combat system, and the games are -old-. Dirt cheap nowadays, though, while pretty much matching graphically any recent "pixel art" (heh heh) release.

Eador: Genesis is a fantastic suggestion in "strategy" category. Forget the messed up "Masters of Broken World" - even if the game will work reasonably well for you (hah!), the GUI is so bad in the remake you're better off just playing the original. Also, personally think Genesis' sprites look prettier than the silly clunky 3d models (and certainly make the screen far more readable).

Sid Meier's (HAH!) Alpha Centauri (aka SMAC). There's a reason people are still comparing any sci-fi 4x games to it (and so far have not found a worthy successor). A true gem from Brian Reynolds that got polished to an incredible degree. The "story" part of SMAC alone is better than a lot of "RPG" games. The "tech-tree" writing is as bloody fantastic as it is well researched and envisioned.

Master of Orion 2. For "galactic scale" games, it's pretty much what SMAC is for "planet-side" ones. Also still waiting for a worthy successor.

Master of Magic. It's to fantasy 4x what SMAC and MoO2 are to their respective genres.

Battle for Wesnoth is great and free fantasy TB strategy. Get it.

Edit: Also, this list cannot be complete without mentioning "Steel Panthers." The amount of detail that went into that game, and the depth of its combat system, is still immensely impressive, even after all these years. You can also find free updated versions around the internet, though personally I'd recommend the original SSI release because it's still that good.

I consider all of the above a "must play" for anybody genuinely enjoying turn-based approach to gaming. No excuses.

***

"Recent" honorable mention tacticals:

Expeditions: Conquistador is a very interesting blend of tactics and story-driven RPG elements. Good game.

The new Shadowruns are fun, and found them a pleasant surprise. Pick any, and won't go amiss.

Legends of Eisenwald. Solid mix of RPG and tactical TB battle system.

Dead State. As above, except with zombies instead of pseudo-historical opponents.

Battle Brothers (still in EA on Steam, but shaping up very nicely). Finger-licking-good tactical combat system, combined with sandbox-y "open world" and proc-gen. Good times.

Underrail. Personally think it's another dark horse cult classic in the making, the game is that good.

Space Rangers (if you set the options to turn-based). Huge sandbox-y game. In space.

Aforementioned Xenonauts. Didn't really jive with me as well as X-COM, but that's a high bar to clear.

UFO:AI. It's free. While still very much a work in progress, it's highly playable, and beats Firaxis' "X-COM" with both hands tied behind its back. Also, did I mention that it's free?

While speaking of "UFO," the UFO-After... series. Again, not exactly X-COM, but I enjoyed it well enough to freely recommend checking out. It helps that you can mod it quite a lot (and people did).

Temple of Elemental Evil. It has its rough edges, but after the entire cluster of its initial release got cleared it's a surprisingly deep and engaging game. Definitely recommended if you're into RPGs as well.

I'm also partial to rogue-likes that, by the nature of their usual control approach, are technically TBs. First and by far the loudest recommendation would be Dwarf Fortress played in Adventure mode (no, really. Dwarf Fortress is THAT awesome, and it's two games in one!). Then either Tales of Maj'Eyal, Rogue's Tale, or Dungeonmans, in no particular order.

Lastly, Silent Storm - not a new game, and I wouldn't consider it on the level of either X-COM or JA2 "must play," but a good title on its own.

***

"Recent" honorable mention strategies:

Dominions 4. Ok, so you don't actually issue orders DURING the pausable real-time battles (you do that before the fight), but all of its strategic gameplay is turn-based (and the game never gets enough love). Awesomesauce.

Pandora:First Contact. A lot of people have not even heard of this awesome fast-paced 4x. Worth a gander.

Thea: The Awakening. Actually, I'd more likely place it in the "tacticals" list due to its tight scope, BUT the tactical combat is... a card game (pretty neat, though), so didn't to avoid confusion. Really recommend checking this one out, it is as difficult to pin down genre-wise as is engaging and full of gaming goodness. To give a clue... it's a "3-X" (eXplore, eXploit, eXterminate, but NOT eXpand XD) survival RPG settlement management game with the aforementioned card-based challenge "battles"... and that probably doesn't cover all the elements.

Age of Wonders (still prefer Shadow Magic to the third, tbh)/Fallen Enchantress: Legendary Heroes/King's Bounty/Heroes of Might and Magic (at least the old ones until about IV, maybe V... afterwards they became crap) - all will scratch the itch, and arguing about which ones is better is so subjective as to have little sense. Can't really go wrong with any.

Lastly, a jab at the Wasteland series. The first one was great when it came out, but its limitations are pretty apparent nowadays. The recent sequel left me extremely disappointed with its blandness. Perhaps the long-after-release patch enhancing combat fixed that, but I doubt it.

Hope this helps :)

No mention of Final Fantasy Tactics yet? For shame. :P

Tactics Ogre too.

It's little bit older, but really good one.
Spellcross - where a contemporary Earth military fights for survival against an extradimensional invasion of orcs, undead, harpies and other fantastical creatures.

So... How about Darkest Dungeon? It seems to fit the requirements to the letter and it's a rogue-lite, so it's designed to be played in short sessions.

errr nope! suppose not!

why was I thinking it was?!