Ok, here's one suggestion for you to consider. Take level
Taxing 18 from Lemmings (titled "Tribute to M.C. Escher"), and make the following stat changes:
- reduce number of lemmings to 10 (optional but that's what you want anyway)
- require 100% save (ie. no lemming can die)
- remove the 15 bombers given (optional since level now requires 100% anyway, but I'm guessing you won't mind not having to implement bombers)
- remove the basher (
required to make the level challenging)
- if your game will display the name of the level, rename it to something else (optional, but makes sense to change the name as we're deviating from the original level anyhow)
The result is a pretty challenging level (especially compared with what you get from the official levels, even the ones rated "Mayhem") that nevertheless does not require glitches, timing nor super-pixel-precise moves to solve. I've attached screenshots here showing what the solution looks like from start to finish. PM me if there are still things about the solution that you still don't quite understand from looking at the screenshots alone.
Here are some cons I can think of for using this level:
1) perhaps the solution is too challenging for the audience of your game?
2) it's a little tedious (takes a bit of time) to execute, due to all that building you'll have to do
3) it only features 2 skill types, builders and floaters. But then again, that may be a pro since it also means you won't need to implement the other 6 skill types in your game.
[edit: in case you're worried about somebody stumbling onto this forum and therefore this post via Google, I can always remove the attachment with the screenshots from this post after you decide to take this suggested level for your game]