Fantasy wars is similar to Panzer General, and it is a really good game, well worth a purchase. There is also a sequel to it called Elven Legacy (which is a bit more forgiving, Fantasy wars is darn hard. If you get Elven Legacy, get "Elven Legacy collection", it contains all the expansions).
While you say that you prefer Fantasy or Sci-fi to military (I agree with you, those are more interesting), there is one particular series that I think you should check out and that is Jagged Alliance, the second game in particular. This series offers deep and rewarding tactical gameplay and it has a solid CRPG element as well. It is by many considered one of the all time greatest of its genre, and a game that I'm sure will get recommended by more than just me.
We do of course have the classic Master of Orion series. The second game is by many considered to be the best 4X space of all time. I don't entirely agree, I'm partial to Emperor of the fading suns (which is hard to find, and dislikes anything later than win98 due to its videos (you can get it to run with a bit of work)) and Stars!, MOO2 is the more popular game.
Age of Wonders 1 is my favurite "Heroes of might & magic style" game. It has its own flavour in terms of gameplay, many different and diverse factions and it also looks very nice. A small but fun thing is the fact that each unit has a description on how it fits into the world, and this can sometimes even be a bit lengthy. It does give a whole new sense of immersion which I think HOMM and the later AoW games lacks.
Sid Meier's Alpha centauri is a must play as well. It takes most of what was good with Civ 2 and transfers it to a Sci-fi setting. It is a shame that the GOG version does not contain the expansion, but even the vanilla game will last you many hours (this is one of those games that never leaves my computer).
You said that you like Incubation, have you tried the other Battle Isle games? They are not similar to incubation, in fact Incubation was a bit of an anomaly, but they are good. Think Advance wars and you will have a decent idea about how they work.
TBS/TBT is my second favourite genre, so if you want more suggestions, just give me a shout.
Post edited December 15, 2011 by AFnord