johnperk: This is a tough choice I could almost just draw a name out of a hat and be satisfied with whatever. Beyond Good & Evil seems to be one of the highest rated action games on gog with 3942 votes beating both POP:SOT and just barely by Psychonauts.
I heard POP2 wasn't that good. Do you need to play the POP games in order? I heard WW was better than Two Thrones.
If you want a well-made Zelda-style action adventure with elements of various other genres (such as stealth), a charming cast of characters and an intriguing storyline, try Beyond Good and Evil. It does feel a bit rushed towards the end, though.
If you want more swashbuckling action and excellent platforming with puzzles, go for Prince of Persia. Each title in the series has its own pros and cons, but the core virtues are present in all of them.
Sands of Time's only real flaw is that the combat is rather repetitive and becomes somewhat tedious after a while. It also throws in some light escort-mission bits later on, which are a bit annoying, but not too bad. The game does shine in almost every other aspect, though, especially the characterizations and narrative.
The second one, Warrior Within, is often bashed for its radical shift in tone towards being more "dark". Personally, I never had an issue with that, as the well-executed story- this time revolving almost entirely around time travel- kind of warranted it. It was a bit unnecessary, although if you actually read the original "Arabian Nights" stories, you'll notice that a lot of them are pretty grim and violent as well.
In terms of gameplay, WW rectifies pretty much every flaw SoT had. Especially the combat system has been improved immensely, it flows much better and is significantly more varied. The game is also structured a bit differently than the first one: While SoT was very linear (not in a bad way, mind you), WW is basically a metroidvania, where you often revisit certain areas with new abilities or on different paths to progress. That gives it a sense of taking place in a an actually complex location, rather than just a series of rooms to traverse.
Two Thrones retains most of WW's improvements, but also returns to a much less dark tone for its setting and story.
For some reason, they decided to cram in a whole bunch of other gameplay mechanics, like stealth sections, chariot races and timed sections. Those don't work nearly as well as the "core" aspects of the series and feel a bit out of place. Also, unlike in Sands of Time, the linearity is very noticeable, to the point where it feels like the game is often heavily railroading you towards a particular destination, in part due to the above mentioned "new" mechanics/gameplay elements.
It's not bad at all, and it does a very good job at concluding the storyline for the series, but it does suffer from seemingly succumbing to some of the then emerging "modern" trends in gaming.
I'd say that playing them in order isn't strictly necessary, at least for SoT and WW, although it would be beneficial, whereas TT's story will probably make very little sense without having played the first two.
Don't bother with Prince of Persia (2008). That's one of the most boring and tedious action games I've ever played.