Another to try if you can find it real cheap ...
(Let me first move myself behind this thick flame proof shield)
... is Warlord IV Heroes of Etheria. Turn based all the way.
(I know that even now a moderator is reporting me to Brad as a dangerous lunatic!)
When Warlords IV first came out, it had a hideous memory leak and numerous other problems besides. Now, finally, five years after release the publisher Infinite Interactive in AU has gotten the money to fix their old game. Patch 1.05 has fixed the problems far as I can tell and added some new stuff like fog of war and a high level hero, Galadriel, for the campaign. Galadriel's castle is Goldshire. (heh heh) KGB has a patch 1.05a with further improvements and is at work on an even newer patch with lots of great stuff. Patch links available at Warlorders.com.
Galadriel's party members level up with incredible speed, which is helpful against the maniacal AI which is not the sharpest tool in the shed. Your 3 member retinue is persistent and they and your hero level up ever so often. Combat takes place in arenas and is automated. All you do is select a party member to go out and combat with whatever the AI sends out. Bit of tactics involved, bit of chance too since some things can lure out your weakest party member, or assassinate heroes, or do damage to the party as a whole. Towers shoot arrows, and archers in the party get a shot when each new combat starts. Siege engines blast away at towers. Pretty simple. If it is obvious you will win, just tap spacebar, instant resolve.
The campaign is not all that long, but with the optional areas pretty good size, and worth doing once. Then there are some new supplied quest maps to go with the old maps, and the random map generator, and a very easy to use map editor. The maps are quite large, by the way. Exploration is one of the things you do a lot of, capturing cities along the way, exploring ruins where you might find neat stuff, the usual. There is one quest with four parts on each map, bit challenging to complete sometimes, because the maps are quite large.
I persist in playing a bit of W4 HoE from time to time because it is such a fast game for a turn based game with so much going on every turn. Gameplay is not just your retinue group. You will have a number of parties who each turn will be up to something different.
The graphics appeal to me, your mileage may vary. There are 10 playable races. Galadriel is an Elf, but the optional areas will eventually give her the ability to lead any of the races including demons and undead, though only in the campaign and its optional maps. So you can try 'em all. Warlords 5 is planned, but no estimated release date yet.