Civilization V plays quite differently from IV so you might consider that, I know I didn't like IV but am hooked on V.
In the sam "Total War" genre, I'd suggest King Arthur - The roleplaying Wargame. It can be a bit rough around the edges sometimes but I enjoyed it quite a lot.
Mount & Blade?
