Some of the things to do for the main quest would be to revamp the companion system so that all three can join, and the stage route so that it's possible to grab all three in one run without actually being forced to meet any one of them (even though I know you can decline their offer to join). Of course, we shouldn't forget to write the storyline accordingly to account for all possibilities (all three joining, any possible combination of two or just one, or no companions at all).
I agree with VladCT about having all companions with you. This of course means that the path system of CV 3 would have to be changed up slightly in order to make this possible. The only way that comes to mind is the choice selection that we had in Rondo of Blood. It didn't matter where you were in the game, you could go back to any stage you wanted. This is probably the best course of action.
Great minds think alike! I have all that already in a design document I wrote up this week.

I redesigned the map to allow the player to get grant and then allow the user to branch to the stage where Sypha is and finally allow the player to go to the caves instead of forcing you to go to the ghost ship. That makes a single route that allows you to get all the party members. I also suggest in my document using the same sort of menu system as RoB uses to allow the player to easily access any stage they want after unlocking things. I also go into detail about how the ending sequences for the main quest should be handled so that it changes based on which party members you've collected. This will provide some replay value. I also suggest having alternate endings for second quests where the player will be able to play as Sypha, Grant and Alucard on their own in "what if..." scenarios where they go defeat Dracula on their own. After that is when I came up with the idea of throwing in some CoD back story.
The only thing I disagree with is having CoD melded in with it. It was a terrible sequel and really didn't do anything to help elevate the CV 3 story more then it already was.
That doesn't mean we can't use the content they created in order to make something better. Besides, I'm talking about CoD's back story, not the exact same stuff that was in CoD, but rather what was in the manga which is basically a self contained story that runs parallel to the events of CV3.
I think this is cool too. The only ones to have upgradeable weapons were Trevor and Alucard. Both Grant and Sypha were left without which is kinda weird when you think about it. Sypha's weapon could be a simple stick which upgrades to a wand and finally to a sorcerer's staff. Grant's weapon could still be the tiny dagger which then upgrades to a bowie knife and then finally a pirate's cutlass or scimitar. Trevor's whip obviously. As for Alucard I think his ball of destruction should remain his primary weapon of attack except make them stronger. And as for upgrading them, have it so that he starts out with the tripple shot fireball rather then just one. When he upgrades, the three shots change in look and color and the final upgrade would be the two-shot hellfire spell as we know it from SoTN (you know the one with the two huge black balls of fire? that one).
That was pretty much my idea too, but I thought to limit it some. For instance, Grant and Sypha only get one upgrade since their talents are more in acrobatics and magic respectively. So I was thinking Grant would get his Dagger from the US version and he could get a short sword as an upgrade to increase his range and damage a little bit. For Sypha she's get a holy staff upgrade. The staff itself would be exactly the same except it creates a spark/flash of holy energy when she uses it that lingers in mid-air for 2 or 3 frames. It would extend her range and be a very different way to fight as opposed to all the other characters.
As for Alucard, I honestly never liked the balls of destruction. Plus you don't want to over power him. I thought to model him more on his SotN incarnation. Specifically, he get's to use his eponymous sword. It would start as a plain blade and each (of 2) power ups gives it an energy field like the one it has in SotN. I thought to model the animation on the sword attack from "Dragon Fighter". He'd be the only character that can use most of the same sub-weapons as Trevor, and he'd have Hellfire, Summon Spirit, and Dark Metamorphosis as his exclusive spells. He'd still have his bat form, but I'm iffy on including the wolf and mist forms.
Hector would be different, but still molded into the CV3 system. My first idea was to treat his main weapon like sub-weapons, in that instead of upgrades he would be able to pick up a variety of weapons that replace the one he currently has. Instead of sub-weapons he'd have the IDs. They would be picked up like sub-weapons, but they would be upgradable by picking up power ups. They follow you around, but only attack when commanded to. They would give Hector specific abilities to. So having them is made important because Hector won't have any special abilities on his own.
Here's the document (not finished):