That's a tough one. Both games are very good, and I have spent countless hours playing each one. The original achieves a wide variety of puzzles with just eight skills, and many skills have multiple potential uses. There are, however, a lot of builder-intensive levels and simple "hero" levels that pull down the puzzle quality a bit.
Lemmings 2 has a lot more skills, some of which are very welcome additions. New skill types like the Jumper, Platformer, and Laser Blaster can create an even larger variety of puzzle solutions; however, I feel that some of these skills are underutilized, meaning that they have a lot of potential uses that are not seen in any of the levels. Some of the other new skills are almost completely redundant. Why add skills like the Club Basher, Scooper, and Stomper when the Basher, Miner, and Digger already exist? In addition, several skills (e.g. the Diver) are rarely (if ever) used, and several of the interactive objects (e.g. cannons, chains) just seem out of place for a Lemmings game.
In the end, I went with the original by a close margin. It feels more polished and complete, and the number of challenges we've come up gives it much more replay value than Lemmings 2.