The Last Express... It's an original, very unique game that really pushed a lot of new ideas, but as I'm sure I've said before, I got the game back in the late '90s (for not much more than this $5.99 too, I think) because of the widespread high praise it received, and just didn't like it all that much. It's probably worth trying anyway, because it is pretty original and interesting in both art and game design, but it's definitely not something everyone will like. I'm more on the dislike side.
First, I've never liked timed games much, and that's how this whole game works. The whole game's set on the train, so there are a very limited number of places to go. It's a living world of sorts, so each character follows specific movements and is at certain places at each time, irregardless of what you do. You often have to be in multiple places at once, or hear a conversation and then rewind and go somewhere else to hear some other conversation or do something you couldn't do until after hearing that conversation and figuring out what you're supposed to do next. As a result the puzzles definitely can get tricky, from what I remember. You have to keep going around the train following people, solving puzzles, etc, always with the tension of the ticking clock and the time limit there, and the challenge of where and when you need to be. There are also fight scenes with gamers who only play adventure games and such may find too hard.
The art style and design is great of course, and I did like going around the train, listening to the conversations, and stuff, but the time elements just make it so frustrating... back at the time it annoyed and frustrated me and didn't find it much fun, after a while. Too frustrating and annoying. I admit I haven't gone back to it in a long time, but my opinion of timed games isn't really changed (for instance Majora's Mask and (to perhaps a lesser extent) Pikmin are other games that I had big problems with because of the timer). I much prefer Lucasarts-style adventure games. The Last Express is original and unique and is worth trying, but that doesn't necessarily mean it's better than more traditional adventure gamers. Whether the game's fun or not is definitely going to be a matter of taste though.
I'm not sure if I want to try it again, it's always been one of those I've vaguely considered revisiting, but I've never quite wanted to actually do it...