Personally, I like being a mover and a shaker in a story, and that generally means that I like a character to be exactly as powerful as he needs to be to dramatically alter the status quo of his environment. This becomes very situational, of course - if I'm playing Phoenix Wright, whose story is about personal-level cases/conspiracies/trials, I only want the main character to have the power to truly get to the bottom of the latest case/conspiracy/trial. If I'm playing God of War, whose story is about betrayal by the very gods, then I want the character to have enough power to topple the gods.
It comes down to a sense of closure - if the character was able to finally bring down that which is causing him/his allies/everyone grief (permanently or temporarily, doesn't matter, I like sequels), then I am satisfied. Of course, this doesn't mean that they should always be able to always punch Cthulhu in the face personally - if they could, through toil and effort, bring about events that then cause Cthulhu to be punched in the face, that's fine too.
Uh, that said, I do want my enemies to be as competent as I am, otherwise I always begin to wonder "how did they get there in the first place?"