Metroid Prime; first time playing it I found it really boring and frustrating.
I returned to it years later and its now one of my favourite games of the 6th generation.
And Shadow of the Colossus for me too. Used to consider it a masterpiece but when I tried to replay it a couple of years back I found the framerate unplayable and wondered how I ever managed to cope with it back in the day.