Chaos Legion has a following? Really? I Got that game awhile back (and still have it complete) and didn't have the patience for it. The character moved slow as
and it didn't helped that I was timed to kill all enemies in a level. I Know later in the game you get a faster character, but goddammit I didn't have the patience for it.
Also looking through my collection and here are my recommendations for you...
Personally one of my favorite gems was The Red Star. It was a shoot em up, but in the exact same vein as Cannon Spike on Dreamcast (if you ever played it). Difficult, but really fun.
Adventure of Cookie & Cream. Fantastic co-op game. It's basically two players trying to race across to the finish line, but they have to help each other out and are on opposite screens.
River King. It's going to be one of those love it or hate it kinda games. Basically it's a fishing RPG. If you like the Harvest Moon kinda games, then I think you'd enjoy it.
Ape Escape 3. Mostly because it's my favorite of the series with all the mini games and it has the Metal Gear Solid 3 bonus game (with cameos and everything) called Mesal Gear Solid.
King of Fighters XI. Full disclosure, haven't played XIII, but XI is my favorite in the series. Huge roster and has a tag in and tag out feature, which is awesome. So basically no longer stuck with the one person dies and next one comes in.
Mortal Kombat: Shaolin Monks. Fantastically well done Mortal Kombat spin off ever. Fun beat em up with so many easter eggs, but stays totally faithful to the over the top violence. Biggest downside is some of the bosses require you to button mash hard and it got super tiring. So tiring that back in the day I had to pass the controller to my then girlfriend because she was super awesome at it.
Amplitude/Frequency. Before there was Rock Band or Guitar Hero, this was one of the first rhythm games from Harmonix. Basically plays like Rock Band: Unplugged on PSP, but a bit more chaotic I want to say.
Mark of Kri. Such a difficult and weird action game. Mostly because the combat system was so...original. Basically you scan the terrain with the right stick and each enemy is mapped to a face button. So you attack enemies that are mapped to a face button, but alot of the missions are also stealth based so you have to take note of any twigs you step on that can lead to either restarting a mission or hell coming down on you. It's fun, but it's so...different. There was also a sequel on PS2 called Rise of the Kasai, but I preferred the first one more.
Mister Mosquito. You play as a mosquito who flies around and tries sucking the blood of a family. If you like offbeat games like Katamari, then you'll probably enjoy it.
Victorious Boxers 1 & 2. If you're a fan of the anime/manga Hajime no Ippo then it's going to be a big bonus since it's the American translated version of the Japanese game. Insanely deep boxing game in how you level your boxer and everything. Fun when you get the basics nailed down, but it's nothing like Fight Night. If anything more simulation.
Shinobi/Nightshade. Not a bad action game by any means. It's definetly one of those quick reflexes, but harsh difficulty kinda games. It's sequel Nightshade though was much more forgiving. Though I sorta thought of it as XBox has Ninja Gaiden and PS2 has Shinobi, though not as super polished as NG on XBox it still has it's moments.
Klonoa 2. I'm surprised you don't have this. If you enjoy platformers then BUY THIS GAME.
The Warriors. My favorite Rockstar game and one of the best movie to game adaptations ever. It's basically a beat em up, but with so many extra things that make it awesome. Like every weapon has a brutal finishing move or environments can be used to slam people against. You can steal car stereos for cash and mug people. Plus there are so many extras like a Double Dragon inspired beat em up and goddamn wheel chair racing. WHEEL CHAIR RACING! LOVE THIS GAME!
The Thing. The gameplay will be dated when you play it I'm sure, but goddamn it's a fantastic survivor horror game in not knowing who to trust and being overwhelmed by paranoia. Also even at the time it was a difficult game simply because you didn't know what to expect.
Psi Ops. Basically you play as a telepathic and toss things around. I Describe it simply so because it is a simple concept, but I found it to have solid mechanics on par with the Gravity Gun in Half Life 2.
Oh and Shadow of Rome. Stupidly gory for a Capcom game as in half the game is spent in Gladiator battles where limbs go flying and the other is spent playing as a different character doing stealth based levels where you hide behind crates and knock out guards with vases.
Ugh, I think that's it for now. Hope that's some help in you finding things.