After giving it some thought, I'd probably restructure the majority of the game in its entirety. The end result might look something like this:
After saving Cain from the Skeleton King, Cain reveals that the knowledge necessary to comprehend the falling star is beyond his ken. However, the rogue Horadrim Zoltan Kulle may still have references to it in his library. Cain sends the hero to track down the location of Kulle's library, only to stumble upon Kulle's soul itself, linked to a replica soulstone that Kulle himself made. This would give Kulle the chance to interact with Cain and perhaps be viewed as a more tragic, potentially repentant figure rather than a mustache-twirling villain. Plus, it makes Cain's death that much more tragic if we see him forgiving Kulle through Act I.
The quest for Kulle's library is moved from Act II to Act I, with the desert tunnels replaced by ancient crypts and the library actually *looking* like a library, rather than an arcane mess. There, the hero learns that the falling star was actually a shard of the crystal arch falling. Dissension amongst heaven's ranks--foreshadowing Maltheal's betrayal in RoS and the Angel of Wisdom's disappearance--has allowed the remaining Evils to enter Sanctuary and, through Sanctuary, the Heavens.
Act I ends with the hero seeking Kulle's black soulstone, which was taken as a relic by Archbishop Lazarus (last seen in D1) and hidden beneath Leoric's manor. The act ends with the hero finding Tyrael locked in combat with The Butcher and Lazarus himself, newly risen as a part-human, part-demonic horror. Tyrael tries and fails to keep the black soulstone from their hands, as Lazarus escapes with the stone, though the Hero defeats The Butcher.
The hero, Kulle, Cain, Leah, and Tyrael travel to broken remains of Worldstone Keep (the site of Bastion Keep) to investigate the fallen heavenly arch and the devastation it has wrought. In traveling to Worldstone, cultist followers of Lazarus constantly harass the hero's party, seeking to take them out before they can arrive. In doing so, they learn that Lazarus is attempting to use the ambient arcane energy of the shattered Worldstone to open a gate to the Burning Hells.
The hero pursues Lazarus into shattered keep--yes, this is where we get the crazy "Arcane Sanctuary" dungeon--just as Lazarus completes his ritual. Casting the Black Soulstone down into the crater, a gate to Burning Hells appears, with hellish legions pouring forth and spreading over the globe. After defeating Lazarus and claiming the Black Soulstone, the hero finds finds Bastion Keep under siege by Azmodan's forces. Attacking from the rear, the Hero must fight his way back into the keep where Azmodan and his lieutenants have overtaken Cain, Leah, and Tyrael. The hero must confront Azmodan in amongst the shattered, shuddering ruins of the keep. Unfortunately, Cain has died from his wounds in the siege. This comes with further bad news: Tyrael reveals that Belial, Lord of Lies has made it through the portal, heading for Caldeum.
The heroes arrive to find Caldeum in utter chaos. Cultists roam the streets, preaching apocalypse. Emperor Hakan's guards struggle to keep peace against citizens desperate for food and security from insidious serpentine demons. The hero works towards saving the populace, entering the sewers to face down the sibilant Iskatu, a serpentine minor demon lord who serves Belial. Meanwhile, Kulle begins coaching Leah in the arcane arts, as his intangible form cannot manipulate the energies of the Black Soulstone. While hesitant, Tyrael agrees to trust Kulle for the time being, so that Belial's soul can be trapped and shattered on the Hellforge. However, Leah begins having visions of her mother, Adria, communicating with her through the Black Soulstone. Foreshadowing ensues--there should be a number of these through Act III, to say nothing of actual lore found in Act I--geneology entries would make a ton of sense in Leoric's manor.
Tyrael, meanwhile, begins accompanying the hero through Caldeum, in the hopes to actually sniff out Belial. Doing so includes excavating several Horadric repositories, now overrun with demons of greed and avarice. Dialogue with various NPCs through this section should indicate four primary suspects: Ashaera (yes, the Iron Wolf Captain), Guard Captain Jim Bob, Merchant Gary, and Vizier Seems-Like-An-Evil-Guy. In a not-quite twist, Tyrael accuses the Vizier, only for the hero to find that they've just placed an innocent man in the hands of Belial's mortal form: the Guard Captain. The Hero must race down through the dungeons beneath Caldeum to stop Belial from sacrificing the Vizier to open a Hell Rift in the depths. He does so and Leah traps Belial's soul within the Soulstone.
Arriving at Pandemonium Fortress, the hero, Tyrael, Kulle, and Leah set out through the Fields of Despair to the Hellforge, in preparation to shatter Belial's soul. Entering the City of Dis--Hell's great foundary--the hero faces legions of demons (like, perhaps, those big hammer guys from actual Act IV!) en route to the Hellforge, which is defended by Dispater, Hell's new forgemaster. After dispatching Dispater, the Hero's all set to have Leah destroy the Black Soulstone....only for Adria to reach through and give Leah her one last vision: her true parentage.
Activating the Black Soulstone through her daughter, Adria corrupts Leah, transforming her into a new Lord of Terror: Diablo remade. Taking the Black Soulstone, Diablo makes for the partially-shattered Crystal Arch of Heaven. The hero must then fight through the demonic invasion to defeat Diablo, defeat rogue Angels of Wrath who believe the Hero's very presence defiles Heaven, reclaim and shatter the Black Soulstone, and end the demonic threat for the moment.
That leaves us set up for Adria as a big bad in Act V as well as Malthael's defection from the ranks of the archangels.
Coupled with all this, I'd actually change the followers:
Act I: Tyrael, Fallen Angel. Give him abilities similar to that of the Templar--lots of melee and defense.
Act II: George, archer/defender of Bastion/Worldstone Keep--abilities similar to the Scoundrel, with ranged attacks, increased attack speed, and the like.
Act III: Ashaera (only after discovering that she's not Belial--Iron Wolf mage, with abilities similar to the Enchantress focusing on spells, crowd-control, and status effects (maybe even a "Dispel Magic" ability that could get rid of Walls/Plague pools/Desecration pools/etc.)