General Grievous was one of the biggest wastes in my opinion in the history of computer graphics; many of the redundant mappings on his surface forced a single frame of him in the shot to take up to 40 hours to render. Even though the aperture would be only 740x420, it took many months to render shots with that character in them. To date he is the most complex animated character ever made.
The most complex object ever made in 3D animation was the S.S. Poseidon in the recent movie of the same name. All surfaces of the ship including deck chairs and door knobs were detailed down to the centimetre of the 700 meter ship. It was in the realm of 2,000,000 polygons.
[In comparison, Woody from Toy Story 2 was about 200,000, the Engineer from the Team Fortress 2 video is about 3,700 and a single unit in Star Wars Battlefront is roughly 600]