Hmm

[Ultimecia]

I'm a sucker for Fatal Fury, so if you can get Battle Archives 1 & 2 for PS2 I think you might like it. I intent getting #2 sometime soon. I'm also trying to get the PS2 collection of Last Blade, so I might recommend it as well. If Beat'em ups are fine too, you might as well try Godhand and The Bouncer (both for PS2).

The best RPGs I've played for PS2 were Shadow Hearts and Shadow Hearts Covenant. Forget "From The New World", it's nowhere as good as the first two. Tales of the Abyss is also a great game, for PS2. If you want a real unknown PS2 RPG game, maybe you can try Tsugunai: Atonement, one of the first RPGs for that system. La Pucelle Tactics, Devil Summoner: Raidou Kuzunoha vs The Soulless Army, Shin Megami Tensei 3: Nocturne...
For GC I recommend Tales of Symphonia.
Sword of Mana for GBA, the FF remakes for GBA... Final Fantasy Crystal Chronicles: Rings of Fate for DS (much better than Echoes of Time story-wise), Legacy of YS: Book I & II, Shin Megami Tensei: Strange Journey, Phantasy Star Zer0 . I also would save some money for the American version of Estpolis: The Lands Cursed by the Gods ( AKA: Lufia 2: Rise of the Sinistrals) . If you have PSP, you might try Final Fantasy I (got one extra dungeon featuring a boss that's an amalgam of all bosses in game, it's very hard +_+) and Crisis Core.