Ok I've written up the following mostly to apply for platform, adventures etc. Not really puzzle games, though in some area's the same info can be used. It barely cuts the surface of level design or theory, but could be a useful starting point for others.
When I mention player skills. I'm talking about the PLAYERS skills, their experience while playing. I'm not talking about player character skills and attributes. I thought I should clear that up as I'm sure someone will jump in and mention it.
Level design is very individual to the game and the kind of gamer yo are aiming for. What works for one game, might ruin another. But the four main points of a level are:
Beginning
Don't simply stick your starting point anywhere, have a reason for it. Ask yourself why does the player begin at this point? How would he have got there? Look through other games and see how they've done it, the different methods used for the different styles of games. If you have a storyline, this will help loads.
Reason
Now you've got your player in your level, what's the point continuing? What's my motive to play through this level of yours? It's all well and good having a storyline and an overall final goal, but what's the purpose of this particular level beyond progressing toward the final goal? You could have the greatest idea on the planet, with the most amazing end of game ever. But if your levels are simply go from A to B. Then people are going to get bored. Include extra's, such as coin collecting, or special power-ups, secret area's or side quests. Your level may still be linear from start to finish, but mix it up and give the player more to do, they'll be glad of it.
This doesn't just apply to the overall levels, but absolutely everything within them too. If something doesn't have a reason for being there, then it isn't needed. This even applies to intentional red herrings or McGuffins (an object that isn't really important, but gets the players attention for whatever reason or moves the game along), perhaps to attract a players attention to a specific area, or to continue the storyline in the way you intended, not just put there for the sake of it.
The player isn't you.
Always bare this in mind. You might know your levels backwards, and know exactly how to do everything in them. But your players wont, so don't make things too obscure. Yes hiding a key to get to the next level, inside a rock hidden in a lake might seem challenging to you, but ask yourself "why is it there?" Drop hints elsewhere. The general rule of thumb "if it's required to progress, don't let the player find it by chance"
End
So you've come all this way to the end... of the level. I know it's not the end of the game, but I'd like some kind of reward for all that effort. Perhaps a bonus score for speed, or a piece of a map, anything really, don't just move onto the next level.
Better yet, a nice big boss character. Make it creative on how to beat one of these, perhaps using the skills you learned during that particular level.
Always reward the player for doing a good job.
---
The first level - Appearance
This is the first part of the actual game that the player is going to see, they're going to judge your game ENTIRELY on this first level. This first level is your sales pitch to the customer you're trying to sell that expensive car to. Everything depends on it. You'll find just about every game out there, the first level, map, location etc. will almost always be the best looking and best designed.
The first level - Tutorial
At the same time, it also has to serve as a tutorial for your game. Pretend that the player hasn't read any instructions or played a game like yours before, they've just picked up your game and began playing. So now you have to introduce them to your controls. The exact way you do this is entirely up to you, and greatly depends on the type of game you've made. Bare in mind the following points though.
A quick fire shoot-em-up is going to attract people with shorter attention spans, or just looking for something fast, quick and simple. So pages of instructions forced upon them will have your game shut off faster than it takes to load the first level. Consider icon displays within the game, showing quick to understand commands. For example an icon of the left arrow key with a single word "Left" next to it, hovering above the player and not pausing the game. Simple, to the point and not interrupting the game (have it fade quickly in, then fade out after they've used the key).
For a more strategic game, make your first level or levels into actual tutorials, with more in depth information. But make it possible to skip these tutorials entirely. Nothing kills replayability more than being forced to go back to school each time you start a new game. Use an .ini file to store whether the play has done the tutorial levels previously, if so, automatically disable them. The player will like that.
Playing curve
Your game should always be reasonably easy to begin with. Don't make it so simple a player could do it blindfolded, give SOME challenge, but try keep within the tutorial like boundaries. For each level, introduce new challenges and problems for the player to overcome, while reusing things they will have learned previously. Mix them up a little, gradually increasing difficulty in a smooth curve. If you suddenly make a level far too difficult than the previous one, it can infuriate players and put them off wanting to play further.
If you've made it well, a player should notice the difficulty increasing, but not feel that it suddenly becomes impossible.
Multiple choice levels
A multiple choice level, or area. Differs slightly from regular levels. While it still has a beginning and end, and a reason for everything within it. It isn't linear in the traditional sense. The player should be able to go where they like (within reason), and complete whatever tasks the level presents, in a variety of ways. Include different obstacles for the player. Have an easy route, a difficult route, a complex route. Don't make them too obvious, allow the player to discover the various means to an end on their own.
Linear layout
So you've decided where your player will start, you've come up with a reason to go through the level, and have a nice reward at the end of it. Now you need to decide on its layout, baring in mind the playing curve, the players skills and what they've learned at that point, and of course the storyline. Don't make it a basic affair where all you do is go right, jumping or shooting enemies as you go. Remember those obstacles, challenge the player. You can move away from being too linear in some cases and have basic maze like paths, a few dead ends (but not too many, they get annoying, fast). Don't punish the player for going the wrong way, how do they know it's the wrong way? Perhaps have a little something waiting for them there if they do, be it an enemy or maybe some power-up or a gold coin. Shake things up a bit.
Multiple choice levels follow a similar layout, just a bit more in depth and more open to player choices.
Automatic scrolling games are more limited, and except in a few cases, will usually just scroll in one direction. Use that to force the player into making choices quickly on how to survive past that part of the level.
Sandbox levels
A sandbox level still has a beginning, an end, and a reason for everything. But what the player does in the level is up to them. They can continue on with the "main storyline", or go off and do their own thing. These are the most complex types of levels, because you have to plan for lots of creativity on the player part. Give them plenty of things to do if they choose to say to hell with your storyline and play how they want to play.
Sandbox layout
The biggest mistake most will make when creating their first sandbox layout, is letting the player go directly to any part of it. This is not how it should be done. Just because the level is completely open and the player can do whatever they want, doesn't mean one big open area. Create winding paths, obstacles the player has to go around. A couple of dead ends, interesting things to discover off the beaten track, a range of enemies befitting the level and players skill. The odd secret to find. Bare in mind though, everything has to be there for a reason. Did you put a stream there for the player to find a way to cross? Where does the stream go, are there other ways across it that perhaps will be useful to the player later on, or in a different part of the level? Why is that large cliff there in the middle of the level? Never put things in your map just for the sake of it.
Layouts in general, while keeping to a levels theme, try and avoid repetition. Spiked pits or collapsing floors can be fun, but not when there's a whole bunch of them to navigate across over and over again.
In some cases, your game might allow for a player to return through area's they previously went through. Bare this in mind when creating your level layouts. Was a particular level really complicated or frustrating? Does your game require the player go head back through that level or is it optional. If it's required, then reconsider how frustrating or complex it is, as your player might not want to have to do it all over again but from another direction. If it's optional, then make sure there's a reward for getting through it, proportional to the difficult of returning that way.
If the player has to go through a level a few times, consider opening up a different route to the player once they've got past it the first time, so they can avoid getting bored of redoing the same difficult things in the same area over and over again.
Enemies
Regardless of your game, it's levels and it's style. Your enemies should always present a challenge, but never be impossible to beat. An enemy is nothing more than an intelligent piece of your level, therefore it should be appropriate for the level in question. Yes sticking a behemoth at the beginning of level 1 is funny, but if 99% of your players can't get past it, they wont be laughing much will they. This sounds obvious but you'd be surprised just how often a mistake like this is made. Enemies appearing too often, too soon before the player is ready.
A good enemy should prove a reasonable challenge to the players current skills. As the player progresses, so should the enemies. The weaker the enemy is to the players current skills at your game, the more you can allow in a specific area, because they become less of a challenge on their own, more of an annoyance, but in groups can still pose a problem to even the more skilled players.
The harder the enemy, the more likely it should be to have a specific Achilles heel (this is especially the case with boss characters).
Boss enemies - They are supposed to always be the toughest and most powerful boss the player has come across SO FAR. No boss should be more difficult than bosses that follow it.