I'll echo the votes for Two Thrones and Sands of Time, both which I loved from beginning to end. Skip Warrior Within, which is not only filled with adolescent "attitude" and lacking all the charm of the first and third game, but it's also graphically murky, repetitive in both combat and level design, and honestly one of the most frustrating / controller-throwing big-budget titles I've ever played.
Klonoa 2 is fantastic, if you can find it, and if you don't mind colorful first-generation platformers with slightly irritating voice acting.
Beyond Good & Evil is amazing, as is Psychonauts. Amazing humor and storytelling in both games.
Ico and Shadow of the Colossus are spiritual cousins, and both are artful, high-concept 3D platformers, both with an eerie atmospheres of desolation.