How about that he was like Moff in this movie, and in the third movie, becomes the Grievous we know: more machine than man and a prototype of Anakin becoming Vader since his outer identity is shorn away (effectively literally).
And I would agree you do need the presence of the threat more throughout, as well as a longer period of Obi Wan and Anakin being bros in the movie so we can care about them when the wedge occurs.
Something like that, though I think it'd be best to steer away from tying the prequels too closely to the OT (strange as that sounds). I think it's one thing to have Obi-Wan and Anakin as the leads, but having minor characters/terms from the OT regularly crop up shrinks the universe. With Star Wars exposition, less is always more.
Grievous/Badguy/whatever would probably dress in a style reminiscent of the Moff's (and therefore the Nazi's), but I'd probably stick him in something akin to a Star Wars version of a WW1-era German formal uniform). I think it'd be cool if he had some kind of mechanical/cyborg component, maybe an arm and a leg, or an arm/chest piece? It could be reminiscent of Vader, but still distinct (since him going bad is kind've a twist).
Niiiiiiiiiiiiice.
Maybe if Anakin loses, he still - by cutting loose and going a bit Sithy - wounds Grievous badly enough that in EpIII (and the Tartakovsky cartoon), he's his OTL robo-self. This not only does that Vader "rhyme" but:
a) Gives the cartoon some more space to work with and some extra weight.
b) Means in EpIII, you can have Anakin wipe out the bad guy from EpII even though he looks - and is - more powerful than he used to be because so's Anakin.
Extra points if after the end of EpII, Anakin's partly robotic. He's on the way to Vader. And how does he defeat Grievous? Giving in to hate and the Dark Side, as Luke will not do in ROTJ!
Maybe; Anakin could wound him, but he still ends up chopping off Anakin's arm. Definitely agree that he goes down early on in our hypothetical Episode III, to demonstrate how far Anakin's gone.