What episode of Naruto does the Rinnegan first appear in?
It is in fact in episode 135, as can be seen here: (Taken from the end of the episode, sorry about the bad quality)


    


You've to remember that in the earlier episodes, we did not actually see Pain, we just saw these images of the Akatsuki members. But the rinnegan was seen already back then.