The paladin hero sounds attractive because of the resurrect skill, but trying warrior as something as different as possible from a mage could be more interesting. Of course, if playing a mage in AP is lot different from TL then I suppose that may be an option.
I played both KB and AP as a Paladin, but used almost no magic. In fact, I really only used magic during boss battles, and only to counter when the enemy used magic against me. I found normal difficulty to be a bit on the easy side in AP, especially in the 2nd half of the game.
I don't think playing a Mage in AP would be much different from playing one in KB, although I can't speak from experience. My advice would be to just play for a few hours as a Warrior or Paladin and see how you like it.