You can use any tilesets on any theme, meaning you can put Egypt pillars on the Crystal, Dirt, Marble and Hell themes. All terrains from all themes can be put in one level, even the traps too. I sometimes play my Egypt level in the Marble background.
Maybe it'd be interesting to see PSP versions of the Sega Genesis/Megadrive levels. I'll point you to a website that has screenshots for those when I can dig up the URL, or maybe you can try Google.
I went to Planet Lemmings and saw the levels and some of the original levels are smaller.
Is it because of memory space or is the levels too big? There's some that I never seen before. Maybe those are the ones you were talking about it. They all look small, so building one won't take too long to make, but I never played it before, so I'll have to look for the solutions.