Probably a Tauros, a Kangaskan or a Chancey in the safari zone on Blue. Seriously, those things are ridiculously hard to get. Then when Gold/Silver came out, I was like 'meh, no problem now'.
I've never even seen a shiny pokemon before, save the Red Gyarados in Gold/Silver/Crystal/Heart Gold/Soul Silver, watching Youtube videos and using cheats (never caught any because it just didn't feel right).
The rarest Pokemon I've seen has got to be a bloody Feebas; I spent weeks trying to catch one before giving up, having saw how awesome its evolved form was, I really wanted one. Then I found out about the wiki, went on it, saw how impossible it is and said "Screw that! If it may only appear in one of a few randomly chosen squares, forget it." To date its the only Pokemon I didn't catch in Ruby/Sapphire besides Latios/Latias (forget which one I caught and which one I still have to catch).