It's a little too long ago for me to remember clearly. I'm pretty sure the first levels that gave me some trouble are the timed bomber ones, not because it's hard to figure out the solution but obviously it takes some tries to execute it successfully. Tricky 16 for example.
Although I don't remember too much difficulty with it myself, it makes sense that Tricky 19 is the first level that tends to stump new players. The closest analog may be Fun 11 in that it's also a level where instead of trailblazing the path to the exit in a purely forward fashion, you need to turn a lemming around and blaze part of the path "backwards". But of course with Tricky 19 you don't have blockers and need to be efficient with your skill usage as well. So yeah, definitely a step up from the previous levels in terms of thinking. (Yes, Tricky 19 technically has a "fully forward" solution, but IIRC that has its own complexities even more so than the "intended" solutions.)
I vaguely remember Mayhem 5 taking a while. If I recall I didn't realize at first that blockers can turn builders, so I keep trying to set the blocker as close to the edge as possible and start building from as close to the blocker as possible (but facing the expected direction). I don't remember how successful that turned out, but I do remember eventually a "mistake" in trying to execute the aforementioned that led to the relevation that the builder can get turned around by the blocker, and then it becomes obvious what to do.
Mayhem 29's ending stumped me, in fact I don't remember for sure whether I figured it out on my own eventually or whether I wound up peeking at a walkthrough online or something. In hindsight I'm not sure why I didn't see it sooner, given that in some ways it sort of follows the same theme as what you did at the start of the level.
The only one I remember finding problematic back in the day was the Game Gear (and, consequently, Master System, since the two versions are closely related) version of Easy When You Know How... When I figured out the solution, I laughed to myself, finding the title accurate. What you ultimately need to do is bash through the floor at the bottom, so that the presses don't trigger and squash the lemmings.
Ironically, I learned many years later that this is not the solution used in any other version of the game. Easy when you know how, indeed - turns out that you don't know how when you play it in any other version. 
I'll have to take a look at that one of these days. So you're saying in that version, Easy When You Know How isn't just a 20-of-every-skill level that's typical of Fun?
Really curious why the straightforward solutions in "normal" versions of the game doesn't work there.
