For me the DMC4 story was as if the developers did have a complete story in their minds, but because of some factor or two (deadlines?) didn't bother to make it clear to us too, who actually don't know what's happening inside their heads (how dare we!).
I'd change that first so that Nero's origins, Vergil's sword, what the order exactly is, Sparda(?) etc. stuff were answered.
I'd make Dante the main character and Nero an unlockable one - like Vergil in DMC3. Or having them do things like DMC2, each to his own disc.
More costumes. And finally let Dante being able to use the DMC2 costume. I was ticked off when he didn't have it in DMC3.
No time in Bloody Palace. It's annoying to be anxious about time. It's the sickest thing in every game. So no, thank you. Judge us by how much time we used yes, but not limit that time. I might want to play and taunt and mess with my enemies, why should I hurry?
Maybe have unlockable characters such as Trish/Lady/Vergil.