Yuki and the Space Show
Yuki and the Space Show is a tale as old as time -- a tale of a girl and her cat -- more specifically, a tale of a girl rescuing her kidnapped cat from the clutches of a deranged interstellar game show host.
The host, an indeterminately-sized green fellow by the name Zorblag, has a great sense of showmanship (but a poor sense of what constitutes a voluntary decision). Introducing each the challenge of each arena with gusto and aplomb, you really get a sense of how much more he cares about ratings than the well-being of his contestants. (Believe me, it's a very charming set-up.)
As for the arenas themselves, you play them in a determined order with a nice "world map" showing your progress from level to level. Each level is given a very classy title card and a nicely composed introductory ditty. There is a good balance of activities, from puzzles to action to boss fights, with a steady ramp-up in difficulty from beginning to end, all of which have clever conceits (with the kind of creativity I personally envy).
While I didn't have too much issue with the difficulty of this world (my main hang-ups were the moments I forgot the mechanics taught in the tutorial level), I will give a word of warning that this eventually requires some esoteric ZZT knowledge to solve some of the later puzzles.
Highly recommended.