I'd suggest Reign if they do want to stick with the fantasy genre. It runs on the One Roll Engine, so it isn't too hard to pick up, though the mechanics are significantly different from D20. It has plenty of crunch, point-buy chargen rather than class-based, and plenty of mechanics that help encourage RP without really forcing them to. It's also a system that assumes that the PCs are political leaders of some sort within the setting, which is a role that demands some level of thought beyond 'kick down the door, kill everything that moves, steal everything that isn't nailed down'. ...well, usually at least.
While doing a modern game probably wouldn't be a bad idea if you think part of the problem is coming up with concepts, depending on the group Call of Cthulu is not necessarily the best choice. I'd say it would depend on if you know your players can realize when a fight isn't going in their favor and retreat. Additionally, based on the min-maxers I play with, most dislike horror-based games simply because they like winning and being able to defeat things, which tends not to happen in horror. I'm not saying that it wouldn't be worth a shot, but you'll definitely want to run the idea of running such a game past them, and make sure they know what to expect from it.
I will say that, in my experience, most of the min-maxers I've played with focus on optimization do so because they don't want to risk dragging the team down or allowing someone to die, rather than out of some desire to 'win the game'. It's just a suggestion, but a game like Mutants & Masterminds or FATE, where death only happens when the players agree that it's dramatically appropriate, would make them feel freer to design characters that are interesting concepts rather than just mechanically sound.