My vote would be away from a main quest and instead offer more quests that are tailored to different "character sets" or skills.
That way the experience a gunslinger has could dramatically differ from the experience an egghead has or a post-nuclear socialite.
Rather then do quest X again with your new char you do a different quest or approach a different character to see the same basic plot of a quest, but from a unique perspective depending on who you talk to, what that person does and what you do (or can do, skill-wise).
Example:
Main quest plot is that a casino is going to be robbed.
Sneaky char: is going to be a member of those guys doing the heist - either for personal profit (maybe further spreading into the "honor among thiefs" or the backstabbing "there can only be one" free-for-all-shootout) or as mole for the law? mob?
Science guy: while being nosy and hacking various terminals you find some clues that lead you to collect information on the upcoming heist - what will you do? Sell the information for fun? Blackmail the potential robbers? Set up a trap to make it look like a heist gone bad but make off with the spoils?
Tech guy: due to your skilled hands and mind and since nobody knows you, you're approached for some specialized equipment - some heavy cutting equipment, a by-pass module for some data-cables etc.
Charming socialite: a heist went off and it was a big one. Now people need answers, but no one wants to talk. And along comes you with a smile on your face and silver tongue.
etc.