Well, we all know Sonic Heroes didn't exactly excel when it came to the plot... So this morning, with nothing better to do and having taken in a little too much caffeine, I started to think of a way the plot could be improved and thought about starting a little game of sorts.
It's as easy as it can get:
basing yourself on the plot of the game and trying not to stray too far away from it you have to create your own plot for Sonic Heroes.
You may modify/add things to other posters' stories if you want.

So here's my own take on the subject:

Basic concept:
Eggman prepares the Egg Fleet for a big takeover of some random city, from which he will expand his Eggman Empire. To prevent Sonic and co. from getting in his way, he sends an upgraded Metal Sonic and those realistic Eggrobos to mislead them.

Team Sonic's story:
Starts out pretty much the same as in the game, only that Amy jumps in and wants to join the team. Sonic fakes concern telling her she might get hurt and rushes off with Tails and Knuckles.
They go through different areas located far from the city, following the realistic Eggrobos, which are sometimes aided by Metal Sonic in boss fights.
In the Special Stages they have to race against Metal Sonic for the emeralds, Metal can hit them, but they can hit him, too; the harder special stages have them racing also against Team Chaotix for the emerald.
When they reach one of Eggman's bases (second-to-last level) they meet Team Dark and defeat together the boss. Rouge reveals from information she got at that base that the real Eggman is taking over the nearby city and had sent the Eggrobos to trick Sonic.
Team Sonic goes to the city (last level) which has already been taken over and is being remodeled by Eggman's robots.
They defeat the robots and are then cheered on by the inhabitants.

Team Rose's story:
Amy is flattered that Sonic cares for her safety so much, but still she wants to prove to him that she can very well go on an adventure, too. She forces Cream (+Cheese) and Big (+Froggy) to tag along (much like she made Cream train with her in Battle). Team Rose plays the same stages as Team Sonic, but after them, akin to Knuckles in Sonic3&K.
They have to race against Team Chaotix in the last few special stages.
When Team Rose arrives to Eggman's base, they meet Team Sonic and are told that the real Eggman attacked the nearby city, just like them they have to liberate the city.

Team Dark's story:
Starts out the same, but Rouge is not looking for some random treasure but for information, since rumour has it Eggman is about to strike again.
Team Dark's levels consist mostly of high-guarded bases belonging to Eggman and the paths between them. Rouge discovers a piece of information at every new base.
In the starting base they are already attacked by the Shadow androids, thus immediatly revealing that the Shadow in the Team is the real one.
When Rouge discovers Eggman's plans it is already too late, as he has already taken over the city, so Team Dark helps to liberate it.
In Special Stages they race Team Chaotix and have to deal with annoying bomb-throwing Egg Pawns as they get harder.

Team Chaotix' story:
Eggman calls the Chaotix incognito and offers a large sum of money if they collect all 7 emeralds for him. Unlike other teams Team Chaotix has to do something different each time to enter a Special Stage and they usually race one of the other teams (exception are the very first few Special Stages, since they're supposed to be easier).
They end up in the city, too, at the end and help out liberating it.

Last story:
All 4 teams board Eggman's flying ship, where the Egg Fleet that took the city over came from. They help each other out to fight their way through the airship and eventually beat Eggman in a boss fight.
Eggman seems to be defeated and the teams are about to leave, when Team Chaotix snatches the emeralds the other teams had, to give them to their client later. Eggman in turn snatches the emeralds from the Chaotix and thanks them for their job, which is when they realize just who had hired them in first place. Metal Sonic uses the emeralds to go super (like Mecha did in Sky Sanctuary) and Team Sonic has to fight him, while the other teams are busy fighting Eggman's final boss machine.