I second/third/whatever Uncharted 2. I haven't played the first one yet but I adored the second and hope to play the first later on. Final Fantasy XIII is worth getting as it looks like you're an FF collector of sorts. It's not the greatest FF ever by any means, but I enjoyed the playthrough a lot.

Maybe you'd like Ico, too. You might enjoy it even more as it's set in the same world as Shadow of the Colossus (although the game is completely different from what I understand). I think the stories link slightly, too.