I was only about 8 years old when my dad and I first started playing Lemmings, so, needless to say, he beat most of the levels before I did. Here are some of the levels that gave us problems (Please note that this is the PC version of the game):
Tricky 19: I remember my Dad taking a long time trying to figure this one out because we didn't know the trick of sending a climber to the top and mining down.
Taxing 4: My dad kept getting zapped by the traps, and he often lost too many lemmings before he could do something about it. I simplified the solution several years later by taking an outside route.
Taxing 6: We didn't know that the traps only zap one lemming at a time, but my dad eventually beat the level when he learned that he can bash through the top few pixels of steel.
Taxing 7: I kept running out of time! Now, I still usually beat it with less than 15 seconds to spare.
Taxing 11: My dad never did figure this one out -- he was stumped for three weeks! I finally beat it for him.
Taxing 13: My dad kept running out of skills here. I didn't see him play it much, so I don't remember any more details.
Taxing 15: My dad kept trying to bomb his way through the spikes to get up to the exit. I quickly discovered how easy it is to simply build over the hard parts.
Taxing 23: My dad kept running out of builders on this level. Now I can save 100% with several builders to spare!
Taxing 29: When I got to this level, I still didn't know the Climber-Miner trick, so I kept running out of bridges. My dad finally showed me the solution.
Mayhem 11: My dad didn't even attempt this level! He said that I had to do it because my reflexes are better! I beat it with no trouble at all.
Mayhem 28: It took my dad three weeks to beat this level! He kept running out of builders. Now that I am efficient with builders, I can beat this one easily.
Mayhem 29: My dad beat this in one evening, but it always took me several tries to get it right (my builder would keep turning around before I got a chance to bash through the pillar near the middle part of the level).
Now, I can easily beat every level, so I try for 100% solutions.