Way of the Samurai 1 and 2: Fun games, really makes you work to be at least marginally skilled.
Shinobido: Ninjas, plenty of ways to do things, murder people with sushi, explode things, stab people through doors. Be a true mercenary and take jobs from anyone, be skilled enough that they never realise you're working for their competitors.
Persona 3 and 4: The persona series are interesting social/RPG hybrids, tackling a variety of issues, personal opinion is that it became a lot better at P3, though Persona 2 was also very fun to play, it's only at P3 that things really start to take off.