How about some characters have diffrent builds?
So one may be strong, one may be smaller and one is "average"
Smaller = Harder to hit (probably less pixels the enemy can attack) but when hit will most likely die instantly
Average = Would be current one
Strong = Slower but has more "Armor" and maybe melee attacks sometimes even "Bounce" off him after hitting him.
Obviously you could change this with so much stuff. But this is what i came up with!
Goodluck Developing
-Teewoo