Secondly, Gollum really wasn't very good at all in FOTR. It may have only been the briefest of glipses in low light, but it still looks horrible (IMHO). It wasn't until after Peter Jackson and others went to hang out on the set of the prequels and swap CG implementation advice with Lucas and ILMers before they made him look as amazing as he did in TTT and ROTK.
That said the feat pulled off with the performance of Gollum even considering FOTR is nothing short of extrordinary.
When I first saw Yoda in AOTC, I was floored for 2 reasons. 1) It still looked like the puppet version from the classic trilogy, and 2) It did this without sacraficing more natural looking mouth movement.
To me, Rob Coleman and crew had really brought Yoda to life in a way Frank Oz (as amazing as he is) could never have pulled off with the puppet.