Lemmings 2, IMHO, had the most perfect level of difficulty. It took me seven years to complete the game, after buying it in 1993 and finally finishing it in the summer of 2000.
I think I remember being told to save more lemmings after getting a gold piece of talisman - I agree that I think you have to get gold standard on every single level. It is possible, just keep on trying.
The end animation isn't all that good anyway!
Have to concur with the opinions on the two-player mode, although you had to be a passionate player in order to do it. On the Atari ST the two-player mode was unfair because one of the players had to use a joystick. The ST was incapable of reading a mouse from the second port.