Zwei and Viola don't bother me much, I actually like them as characters. And they weren't the first magic users, Zasalamel comes to mind. I don't really want more magical characters, though.
I'd like to see a character with a flail and also a saber+dagger style.
Also, two characters I really want to see are a Spanish conquistador and a native American tribal warrior, inspired by the Aztecs. He couldn't technically be an Aztec as they were destroyed at this point in time (unless he is a bitter and vengeful man who has been taught to resent the Spanish conquerors who destroyed the land of his forefathers).
The conquistador because their traditional armor is extremely badass, in my opinion, and because I think he would be a really unique and interesting new character for the Soul series. He could be the saber+dagger style, or he could use a larger one-handed longsword or something of the like. I'd also like him to have either a pistol or a rifle (or both) that he could pull out for his CE and maybe for some specials.
The Aztec-inspired warrior because he would be the perfect rival for the conquistador and because it would just be cool to have an Aztec. I like the idea of him being resentful of the Spanish for destroying his people. He could even be trying to find Soul Edge to re-establish the Aztec Empire or something of the like. He could use one of those sweet Aztec war clubs. It'd be brutal. And awesome.