> Interestingly, I remember someone telling me that "Toy Story 2" was originally intended to be just another direct-to-video sequel, but it turned out so well that they decided to give it a cinema release.

Yes and no. It was indeed supposed to be direct-to-video at first, and the project was converted to a theatrical release in large part because of the quality of the effort, but when that transition happened, all past work was scrapped, and they started over from the beginning. I'm not sure how much of the story (any or all) changed, but all the animation work on it was scrapped, and they started over with theater viewing in mind.