The Wizard and the Enchantress gohunting for the Black Soulstone *which has shattered in the fall to Sanctuary* because they can sense the evil magical aura it is giving off. The Wizard calls a meeting with the other Nephlam and tell them the location of the 3 Soulstone shards. She herself starts tracking down the shard she believes contains Baal, in her homeland of Xaishi. At some point she is attacked by the Assassin from the last game. (read her short story, and understand)
The Demon Hunter and the Scoundrel realize that the Fragments cannot be destroyed without the Hellforge. They descend into Hell to steal it (because it can be stolen duh). There they also hear rumors of a rogue witch queen rallying the remaining demons for a sinister purpose...
The Witch Doctor goes go back to the jungles of the eastern Continent where he learns of a horrible power growing there, much like it had 20 years earlier. He arrives to find that the soulstone fragment containing Mephisto has once again possessed the swamplands on the Sea of Light.
The Barbarian and the Templar hunt down a now corrupted Imperious in the deserted corners of Heaven, where Imperious has created a kind of nuclear fallout kind of area.
The Monk believes that Leah still lives on in a fragment of the Black Soulstone and he tracks down the fragment containing Diablo (and hopefully Leah) in the Skovos Isles. There he has to use his holy awesomeness to separate her soul from Diablo's and kill him again.
And in the process they destroy the Lesser Evils...somehow. But yeah, I think it would be really awesome to have different story lines for each class. Your thoughts?