I really didn't like Disciples III... Even II was too simplistic for my tastes. Some neat ideas, but overall, played a few times then it languished and I eventually uninstalled it. C4 has a lot of nice mods for it, depending on your taste, but most of them are either dry, or flawed, good for playing for a while* but then they unravel, and you get to wait for the next patch/upgrade/modmod to come out. FFH2, The Three Kingdoms mod and Rhys and Fall are probably the best (Rhys and Fall isn't very fantasy), and the Dune mod is cute (that's kinda fantasy! 8D). But back on point, I'm also a big fan of Dominions 3. There is a Zen to the game which can take a while to pick up, as well as different strategies based on faction you choose. The AI will happily stomp on your ****s without pity or remorse, and the game switches up strategies and play styles from the opening, mid and late games rather interestingly. I quite like it. Once you get the Zen of the game, though, you can learn quickly to win as anyone. It also has some mods, some of which are fun, in the form of new factions with odd playstyles. If you have a PS2, you could play Brigandine, which is one of the best turn based strat games I've played. Warsong from Nintendo days. Also Cryptic Comet has an interesting but overly luck based turn-based "fantasy" game called Solium Infernum (You play a Prince of Hell). Amageddon Empires is better, but it's post-apoc "fantasy". Overall it's pretty slim pickings, imo.
I've played the other games mentioned so far as well, but I think they've been pretty well covered. As for RTS's, I'm not really a fan of the genre. The best two I can recall (for my tastes) are the original Majesty, and the original Kohan games. Both had sequels, both sequels were disappointing.