Here are two quick recommendations, I'll recommend more when I think of more.

ESPN NFL 2k5: Best football game ever, both for the gameplay for gameplay's sake, and for it's (very deep) Franchise Mode. One thing I really love about this game is that player stats actually impact their abilities, compared to other football games, so for example if you have a weak armed quarterback, long passes with be next to impossible.

The Getaway and it's sequel The Getaway: Black Monday. The Getaway has a very well written story, with great atmosphere and mood, helped by some of the best voice acting I've heard in a game, however the gameplay itself can be a little clunky at times. The Getaway: Black Monday is also well written, though it's story does stutter at times, and perhaps due to being more accessible, it feels really easy compared to it's predecessor. The Getaway: Black Monday does have a few choice/consequence scenarios. Overall both games are rather cinematic, featuring strong voice acting, above average writing (both story-wise and general dialogue) and soundtracks that help the mood and fit the setting. Both games can be a little clunky, but that doesn't affect their playability at all.

Used PAL Rule of Rose costs well over $100, and it's not worth the money.

Shinobido: Way of the Ninja is awesome. Stealth action with three factions to serve, and an extra secret ending to achieve. You have to revisit the location maps a lot, but enemy placement changes, and they get better equipped.
You have your own "tower defence" game for fending off enemy attacks on your hideout (if you piss them off), using bears and spike pits. If they do break in, they mail you a list of stolen goods and put them on sale at the market.
There's alchemy, too. Collect mushrooms and brew them into custom buffs and debuffs, like memory-erasing sushi, and exploding throwing balls.
On new game plus you keep all your stuff, and gain ability to steal the bodies of characters to play as them.

I'm in total agreement - replayed it numerous times, and it ties up the background to the classic film nicely as well

Really? Ouch, I got my copy for 40ish brand new at a con a couple of years ago. Then again, I've seen some absurd prices for European versions of games, but still, again that's absurd. I think the game is still worth it but that is still ugh. Sorry that is just rather shocking.

There were some bitching politicians, that made the game hard to find.
See the price tags http://www.amazon.co.uk/gp/product/B001M1AFKQ

I don't see what they were bitching about, the game is fantastic. They probably sucked at it and wanted to make sure no one else was having any fun. :P £600 O.o Ouch, okay £100ish I could rationalize, £150 I could rationalize, but not £600... >.>

Well, you MUST buy those games:

Shadow of the Colossus
Ico
Metal Gear Solid 3 Subsistence
Metal Gear Solid 2 Substance
Final Fantasy X (avoid X-2 and XII)
Devil May Cry 1
Kingdom Hearts 1
Kingdom Hearts 2

Oh come on final fantasy XII was awesome :(

Ivalice is such an amazing world full of rich lore and finally no more random encounters.

Also this is the 3rd reply I said to you in three different threads ;)

Well, I hated FFXII for its plot, for Penelo and Vaan (useless characters ever), this is the only FF in which I can't beat optional side-quests for bore :D

Yes it is, decent story and well worth playing, be aware it has the old classic RE controls, not like the more recent RE games.

Code Veronica is very very good, but I remember it as one of the hardest RE. I played it on Dreamcast, and survive was very hard, but finally I completed it (I also killed a boss with the knife, lol).

Is CV the one with an annoying teenager sidekick?

Yeah :D
But if I remember well, you use only Chris and Claire.
You can control him only during a short section of the game.

Never played it myself, but I've hard that it is. I've also heard that it's one hard motherfucker, and that it's the one other Resident Evil where the knife is useful (the other one being RE4, of course).

Back in the day, Resident Evils suffered from enormous plot holes and certain amounts of ridiculousness that (arguably) somehow failed to compromise the structural rigidity of the series. Nowadays, Capcom doesn't even pretend to care. Where things went tits-up is up to debate, if indeed there is any single point in time and space when it did, but I'm of the opinion that it's somewhere during, or failing that, immediately after Code: Veronica.

Detonator for PS2 is a small CD-based game, but packs a lot of puzzles to utterly confuse you.

While we're on PS2. Someone mentioned The Warriors earlier. Is it worth getting, if I find the usual Rockstar sandboxes dull, and loved Yakuza 1,2,3? I watched the gameplay a bit, and it kinda looks like a linear San Andreas with punching.