I've always been partial to the "there should be a flaw in there somewhere" mentality, kind of like superman and kryptonite.
If you use any magic, make sure there's some kind of cost (in my universe, they can only cast so much before wearing out, as it heavily drains the caster's stamina, or something like that), and make sure it's only so powerful. If the caster becomes god-like, it'll be kind of boring, particularly if said character was "of noble blood and didn't know it, so that's why he can summon "god mode" hehe". Heck, one of my stories has a commoner save the day simply because I'm so tired of it always being some noble hero from a high birth or status. I want an "average joe" to be a hero for a change hehe (similiar to Frodo, but he actually fights well. Obviously he'll have "nobility" friends, but they're mostly just support, not the main characters).
To use something a little less orthodox, in the video game Metal Gear Solid, your character (Solid Snake) talks to one of the scientists (Octacon) that created this super weapon (a giant walking mech capable of launching nukes without creating a trail, think it used magnets to hurl the nukes at targets). It's virtually indestructible, save for this one thing the scientist deliberately left on it. While it's an obvious weakness you can exploit (with Stinger missiles), the scientist says he put it on because he wanted the machine to have some "character" to it, a flaw of some sort (the Metal Gear games have really good storylines too, they'd make better movies with their own in game cinema cut scenes than some of the recent movies coming out lol). The other Metal Gear games are kind of like this too, but with some twists (in part 2, you have to fight anywhere from 3-25 of the giant mechs, and in part 3, you're riding in a motorcycle being chased by that giant mech, which is really cool because that thing moves extremely fast and you're also being pursued by soviet soldiers at the same time).
The point is, have some kind of flaw, or weakness. Sure, magic could cost nothing, but it would make for a weak story, and nobody's perfect (at least in this mortal realm hehe). And yes, definitely make the bad guy stronger, at least initially, or else why bother writing it in the first place? You might as well have the hero wave his hand and smite the bad guy on page 5 and end your story there lol.
Weakness could also take the form of another character. Movies do this all the time, where the hero is seemingly invincible, till the bad guy captures his sidekick/girlfriend. I've seen it go a lot of ways, but usually this will cause the hero to stop doing whatever he was doing to kick the bad guy's butt (if you want to make it more dramatic, have the hero not care about anyone, and is resistant to developing any feelings for anyone other than themselves, probably due to a tragic past, and this "person in trouble" gradually breaks that wall away. Yeah, kind of cliched now, but if done right can be pretty cool). If you go this route however, make sure it's unpredictable (for example, if the hero finds an elixir that can bring someone near death back to life, and then the bad guy captures his sidekick and girlfriend, and tells him to choose who he wants to save, and then shoots both of them. This kind of scenario would be intense, because if the hero cares for both, it won't matter who he saves, since one of them will die regardless. You could "cop-out" and have a 2nd elixir hidden away somewhere, but again, make it unpredictable).
Just some random ideas I'm tossing out (lol, I might have to use some of them myself
). Take it for what you will.
