I can’t ever remember which games came out when, so I had to do some digging around. I’m also generally a few years behind the curve, so take that into account as well. In random order:
Planescape: Torment: Technically released 20 days before the 2000s, but who cares? Text-heavy, but with interesting dialogue, the rare occasion that the haphazard (A)D&D world and its worst mishmash setting, Planescape, felt like a living place that asked to be explored. Gameplay that rewards different playing styles and doesn’t restrict XP or character advancement to combat and a damn interesting story to boot.
FFX: It was the only FF of this decade that I saw played by a friend and wanted to experience. The graphics served the setting and the story, while not pandering to the player, kept players at it.
ICO: In two words: Concise, atmospheric. It used the old adage “show, don’t tell” to great effect and based the game on a few simple mechanics. Mario-like in its simplicity, a haiku of a game.
LoZ:Wind Waker: The animation makes exploring a joy, you can sail around all you want and the story parts are well presented. The plethora of places to explore hearkens back to the original Zelda spirit while it kept MM’s idea of people living their lives. (Hon. mention: I almost chose Twilight Princess on strength of its dungeons alone, but it abandoned some of its good intentions sometime around the middle.)
The Way: An RPGMaker game in 6 parts that creates strong characters with their own personalities and agendas and lets them interact in the game’s world. The city that serves as the stage for part 4 is vibrant and plausible and the last episodes are frantic. A DIY effort that puts established studios to shame in the character department. Available to d/l as an exe.
Aria Of Sorrow: The Castlevania of the decade (Dawn Of Sorrow hasn’t convinced me yet, though a great game in its own right). The castle is huge, exploration pays, the soul system is interesting and there are extra modes if you’re itching for more. (Tangentially: One of the two best Metroidvanias, together with Metroid Fusion).
Morrowind: The huge world available to explore and the customisation options manage to make up and then some for some kinda bland characters. Easily better than Oblivion and FO3 imo.
The World Ends With You: I started playing prejudiced against the setting, the characters and the style, got hooked and quit only after I had finished every single sidequest. Squeenix wasn’t afraid to support its vision, battling was fun and the result was addictive.
Arcanum:Of Steamworks and Magic Obscura: The game’s combat was slow. S-l-o-w. But the strengths of the Fallout legacy carried through to a game where chargen and interaction choices impacted the game, you could play a gun-toting wizard and the Victorian Fantasy setting hit plenty of right notes before steampunk hit it big time.
Mario and Luigi Partners in Time: One can’t call it innovative. It doesn’t have much replay value. But it’s fun, fun, fun and doesn’t sag for a single moment. Humorous to boot and with boss battles that feel as a welcome climax and favor attention over grinding.