Quoting magiclyDelicious,
Playing Avernum 6 right now. Its a VERY good game. There is a lot of reading, which is actually good because it doesn't suck. And they actually used a spell checker. I really suggest people try avernum. I went with 6 since it gives a fully open game window with the interface as an overlay. It also runs at numerous resolutions.
I actually picked up Avernun 6 yesterday. GamersGate had an offer for Avernum 5 (60% off, cost about 7 Euro) and I figured I'd get the latest version together with it. Haven't played much yet, but I used to be a huge fan of the Exile series back in the CompuServe days, and the Avernum games seem to play the same way. Takes a bit of time to get used to more simplistic 2D graphics again, since I've gotten used to state of the art visuals, but looking at how long it's been that I played a RPG with a story that actually "grabbed" and interested me, it's fairly obvious that stunning graphics alone just don't make for a good experience.
As for Fantasy TBS, I'd definitely recommend the two King's Bounty games. KB: The Legend is fairly inexpensive now and a little easier than Armored Princess, though the latter has some nice convenience features (less backtracking) and perhaps a better story. There's also KB: Crossworlds coming out in 2-3 weeks, which is an expansion set for Armored Princess. These games are lighter than Elemental, but I find them extremely playable and highly addictive.
A little deeper, and still tactical, are Fantasy Wars and its sequel Elven Legacy. I'd definitely get FW first, which is pretty much a more modern version of Fantasy General. Both titles have a higher difficulty than what most gamers today are used to, especially Eleven Legacy. They are also very pretty.
The AI isn't the greatest, but the scripting is superb, so it th e computer opponent seems quite intelligent.
AoW2:SM is a classic, and probably my favourite fantasy TBS so far. Someonealso mentioned the Kohan series, which is probably the only "actual" RTS series that I truly enjoyed. Not nearly as twitchy as the typical RTS titles. Kohan: AG is the best of the three games. Also already mentioned was the open source game Battle for Wesnoth, which includes a ton of content, receives updates every so often and has a vivid community. Good AIs.