Shifty, that video you've posted doesn't look "CGI" to me at all. Almost everything is hand painted - maybe it's projected back onto 3D geometry, maybe it's just cleverly arranged 2D cards, but I'm quite sure there's no actual lighting and shading going on most of the time. Which is why the characters stand out so much from the backgrounds, as they're dynamically lit and shaded.
So in my mind it's actually more similar to traditional 2D animation, with 3D characters without cel shading. It does look nice though, but I see no reasonable comparisons here.
Toy Story is an interesting basis though. Thanks to Renderman, there are some elements of it which are still beyond the capabilities of realtime renderers IMHO - the image quality and the geometry complexity. No contemporary video game is even near the 'poly counts' although since almost everything back then was NURBS rendered as micropolygons, it's very hard to compare. And of course AA and texture filtering were already very good, whereas games are still using all kinds of trickery.
Another aspect could be the lighting - back then any type of global illumination solution was way too expensive, so Pixar's lighters used a LOT of point and spot lights and basically "painted" the scene to look convincing. Not even deferred renderers are really able to do that. On the other hand the various baked and approximated GI solutions today might look comparably nice to the audience.
But then again, what is "CGI" anyway? Even without looking at the more stylized approaches, there's a very wide range of possible looks and visual elements to chose from. I mean look at almost anything new from ILM and the new animated Asterix movie, they couldn't be more apart and yet they're both built with Maya and rendered with Arnold...