Well, Graham's portion in the game was completely cut. All the had finished for it was a single line. No one knows how much longer it would have been. The KQ7 novel might hint at some aspects of it, since its told from the perspective of the Valanice and Rosella discussing their adventure with Graham. The ending as a whole was probably going to be more elaborate.
There would have been alot more on Malicia's backstory, how she tried to conquer Etheria and Eldritch in the past, the war between her forces, how Vlad Tepes lost his head, the boogeyman, the Gargoyle, etc. Maybe through cutscenes. Peter Spear printed some of the design documents discussing this background, and those same documents were also properly edited into a summary of events, and printed in the KQ7:Official Hint Guide by Lorelei Shannon.
I think it was said the Gargoyle and Boogeyman would have had a larger roles in the story in particular.
There was going to be at least two more areas of the kingdom, including an area called the "Rubber Jungle". The Were-Woods probably would have been fleshed out a bit as well, and maybe the Swamp?
Peter Spear alludes to there being alot more puzzles planned, some were to be pretty elaborate, he only hinted at one example, IIRC. I forget what he mentioned though. It might have mentioned a couple of item ideas that got cut. I think Colin Farwalker might have had a larger purpose as well. There might have been something along the lines of the last chapter wouldn't have been as choppy as it was, you probably would have switched back and forth playing both Rosella and Valanice and following both paths to save the kingdom.
There was also an extra scene shown in the KQ7 novel just after Rosella leaves Ooga Booga, where she speaks to Attis moments after her mother had entered the woods to Ooga Booga (he tells her about her mother, and that she had just passed into Ooga). They had essentially just missed each other as they passed through the woods.
There is actually quite a few lines cut from the dialogue that can be found in the files, including comments by the Kangeroo rat for nearly every item in the game, many that you normally can't bring to the to the rat since you have already used them by the time the characters reach the rat. He also has a line where he gives the desert an actual name, other than The Desert.
Speaking of things cut, while it made it into the initial release, there was an extra death scene cut in the 2.0 edition. You could be killed by the dragon's tail falling on you, in the original release. No one knows why it was cut, and its a bit of shame.