Blood Omen: Legacy of Kain - a competent Zelda clone with a kick ass story and great voice acting, even by today's standards.
Legacy of Kain: Soul Reaver - a prettier sequel and Tomb Raider clone, all the way down to the block puzzles (which can be annoying). I've never actually finished it, but the story and voice work are once again pretty damn good.
Mega Man X4 and X5 - are fun twice over playing as Mega Man and Zero. Personally, I'd skip X6.
FF:Tactics - although if you have a PSP I couldn't imagine not playing the War of the Lions remake instead. Superior translation, a couple more characters, and awesome cutscenes.
Castlevania: Symphony of the Night - if you've played Super Metroid or any Castlevania on a portable since 2000, you know why I'd even suggest it.
Suikoden 1 & 2 - thoroughly enjoyable 2D RPGs with decent plots, good music, and classic gameplay.
Tomba & Klonoa - badass 2.5D platformers, though Klonoa will be remade soon for the Wii. Never played Tomba 2, but it could be awesome.
Metal Gear Solid - only one I've bothered to finish.
FF VIII and IX - skip VII

D . VIII wins on gameplay (unless you use summons a lot, then it sucks) and IX wins on charm and characters. VII has a great plot, but the poor translation and/or awkward dialog drags it down a bit. It's everyone's favorite though, I just can't get into it any more.
Mega Man Legends 1 & 2- good use of 3D and cool characters.
Vagrant Story - combat is bad ass, story is pretty good too.
Twisted Metal 2 - only game of the PSOne gen that was any good.
Silent Hill - played this one again back when the movie came out. Still creepy as hell. Children that giggle when they stab you in the shins are pretty effed up. Plot is better than the movie's, even if the movie was based off of it.
Alundra - Zelda only it's hard as all hell. The puzzles are pretty awesome, and the plot is pretty effed up (people in town are constantly dying in their sleep).
Valkyrie Profile - though once again, you can just play the PSP rerelease.