I say go for the tactical combat. At least for me, it's the feature that
made Master of Magic. Ah, the wonders of an invisible flying Great Wyrm...
The other real hurdle that's got to be dealt with would be the two realms--Arcanus and Myrror.
...In fact, one would probably want to handle the multiple planes first; once you've figured out how to get two full-fledged maps working side-by-side, I imagine it wouldn't be much harder to set up a third map for the tactical combat engine, especially since the battlefield doesn't have to be very large.
Then, you "just" have to define the combat mechanics, and create a buttload of new graphics for the terrain, units, spells, etc. Fortunately, the Civ IV combat engine already has many of the features needed for the figure-based units in Master of Magic.
Of course, probably the most efficient (yet difficult to achieve) way to build the combat system would be to create something based upon, but entirely separate from, the map engine. That way, you could have the playing field itself hard-coded into the game core, expose a bunch of the functions to python for modibility (modding a mod?), and avoid having to bloat up the map data and XML for the battlefield terrain properties, etc.
As I've stated many a time before, though, this is all no more than just speculation; the very little programming knowledge I have isn't even in Python or C++, but rather Java... Heck, I can't even remember anything from the Visual Basic I learned in Programming I in high school (and the Java was learned in Programming II

).