I was strongly recommended Tactics Ogre after I mentioned I liked Fire Emblem I bought the PSP version, but I need a PSP to play it. Perhaps then you would like to try out either Fire Emblem or Super Robot Taisen, SRT is among my favorite Game Boy games.
Check me if I'm wrong, but didn't Famicom Wars precede Battle Isle. Not to say Advance Wars could not have drawn inspiration from it, but Nintendo had this series for a while before Advance Wars.

http://interplanetary.weebly.com/

Interplanetary is like Scorched Earth between planets.

Bionic Dues and Last Federation added plenty of twists to the turn-based formula, though admittedly the strategy map of the later is more like real time where you can control the speed (similar to X-Com).

Again, if you don't mind a bit of real time that you can pause (ala Baldur's Gate) FTL is downright awesome too.

Another that comes to mind is Disciples 1&2 (not sure if that was mentioned, didn't see it perusing the thread). It's probably closer to HoMM than the above games (upgradable buildings to build units, heroes that explore map, level up and collect treasure), but I still wouldn't classify it as HoMM-like.

Moonbase Commander is another swell turn-based that is definitely non-standard, though probably a bit frustrating if you don't know how to aim (aiming feels a bit like playing a golf game).

In short:

1) Bionic Dues (100% turn-based, totally different)

2) Last Federation (Main Map is RT-slowable/pausable, totally different)

3) FTL (Combat is RT-pausable, totally different)

4) Disciples 1&2 (100% turn-based, some similarities, but overall different experience)

5) Moonbase Commander (100% turn-based, totally different, though shooting feels like a golf game)

If you have a PS3 or a PSP, you could try Valkyria Chronicles ( first one on PS3, parts 2 and 3 on PSP - i just hope that you know some japanese for part 3, as Sega never bothered with a western release).

Think I've said that already, but keep an eye on this:
Telepah Tactics

You can also try an early demo and see what is like.

I think there are some decent fan translations out there if he bothers to make them readable for the PSP.
Final Fantasy Type-0 had a pretty good fan translation.

Most wargames (Panzer General, Civil War General, East Front, etc.) are turn-based.

Other than that there surprisingly aren't a whole lot of non-4X choices, especially if you consider tactics as separate from strategy.

I do know of MAX, which I bought a while back here on GOG but I haven't played it yet so no comment there.

There is also of course Magic: The Gathering. But I assume you are looking for video games only so that doesn't really count...

If you are after something more tactical you should try Frozen Synapse.

Can you mention some strategy games you like?

I really enjoyed The Banner Saga earlier this year, there is a bit of turn based strategy but there is also a fair bit of King of Dragon Passy/Oregan Traily-ness about it.

Missionforce Cyberstorm and Fallen Haven/Liberation Day are also different enough TBS games that you might like.

I wonder why no-one mentioned Master of Orion 2 and the Galactic Civilizations series.

Also +1 vote from me for Lords of the Realm 2 - great medieval strategy game.
And as for M.A.X. - i think it's one of the best (if not the best) strategy games ever created.

I agree. HoMM3 is a blast! I also love AoW and like Disciples. I have to try Eador: Genesis next.
Sorry Sachys, this post is probably more of a anti-recommendation. If you don't like HoMM, don't try those mentioned above! ;)

Sounds like most of the usual suspects have been mentioned except the Front Mission series for consoles.

Banner Saga I would hesitate to recommend. The tactical gameplay is a bit "gamey"... It has an alternating turn mechanic that rewards players for doing things like bringing a squad of only one archer and kiting enemies since the archer gets to move N times as much as the enemy (where N is the number of enemies) and can just keep shooting and moving back out of range.

Fallen Haven is a long forgotten game that is rather good and should be here on GoG.
May be exactly what you want.

http://www.gog.com/wishlist/games/fallen_haven
http://www.gog.com/wishlist/games/fallen_haven_2_liberation_day

I still have the original CD but didn't notice that there actually was a sequel.