I now always play on M/M, with excessive roleplaying.

The thing with "no challange" rather is a problem of the stupid tactical AI: when you usually win each battle, unless horrid insane odds, having the AI throwing even more stacks against you doesn't realy change a thing.