It certainly depends on the type of game, and as always, there are no foolproof ways to increase difficulty, but in my experience, I have found that making difficult games/levels is much, much more difficult than making easy games/levels. Some reasons that come to mind are:
It is very easy to cross the line between difficult and plain impossible. I really enjoy very difficult games, but many times I see that a specific game or level is just too difficult, or even impossible, that I get frustrated. Remember balance is paramount.
Difficult games and levels are mostly about training and repetition. A player should feel that he's getting closer to finishing the level each time he plays and gets better at it. Making a level that creates this feeling is very difficult.
Difficult games and levels tend to have much more variables/entities than easier ones. Be it more enemies, more bullets, more curves or whatever, every single entity has to be placed and set up. Just the setup takes much more time than simpler levels.
The more complex the game becomes, the more possible it is to have a vulnerability that renders your entire difficulty scheme useless. Making sure that the game remains difficult for various playing styles is very difficult.
There are no foolproof ways to make your game/level more difficult, but I have some recommendations for the level designer:
I think you can only make a game as hard as you could play it yourself, not harder. Or in other words, "if you can't beat it yourself, make it easier". Because of this:
Make sure you like the game genre you're playing, and you have plenty of experience with similar games. That means that you're VERY good at the genre. I would say that at least 100~250 hours of play for each of at least 5~10 similar games would give enough experience to lead the design of moderately difficult levels. Extremely difficult games/levels (like IWBTG and similar) may require more time.
Make sure you keep on playing other games while you design yours. It's very easy to get too involved in your levels and make them just too difficult. Also by making levels you will notice new things that you may had not noticed before, and you may want to check other games to see how they deal with those things.
Even so, show the game to other people who have less experience with the title, at least to make sure that the goals of the game/level are clear even for newcomers.
Play, play, play and play the game. For a single action game, it may take dozens, or even hundreds of times to playtest each level to make sure they are balanced. Of course, the more difficult the levels are, the more you have to test them.
Make sure the game is easy to test. If you can change a level without recompiling, cool; if you can change a level without rebooting the game, awesome; if you can change a level without having to go through the entire game sequence, super; if you can change the level as you play it and rewind it to test your changes immediately, ultra-awesome. The shorter it takes for you to retest your game, the more you can play it and the better you can make your game come out.
Don't be afraid to throw away a level and remake it afterwards. As you learn more about the game you're making, your levels will be more fun. The first levels you made will probably have to be rewritten at the end. This also means that:
Leave the first level until last. The first level people play will probably have to be the best designed one, as first impressions count very much.
I have two specific experiences of two indie games I worked on, I would like to share (disclaimer: I made these games. I am including this information for illustrative purposes only. If you want more information about them, there are some links in my user page)
Game 1: action shooting game
Gameplay video: https://www.youtube.com/watch?v=n2t3nw4KQXQ
This was my first full game. Enemies shoot bullets at you, and you have to dodge the bullets while attacking the enemies.
Making the levels for this game was tough. I had played several action and shooting games, and cleared some on moderately hard difficulties, but I have to admit I am no pro-gamer.
The first thought I had was to simply have more enemies as the difficulty increases, and have enemies shoot more bullets at you. Certainly, that makes the game more difficult, but sometimes you will end up in places where there are so many bullets there are simply no way to avoid them. Simply increasing the amount of bullets is just not enough to vary the difficulty of the game.
Another thing I tried was to vary the speed of the bullets fired. It is not trivial whether faster bullets make the game easier (faster bullets mean less bullets on the screen at the same time) or harder (faster bullets require better reflexes to dodge)
It is also possible to make the bullets harder to dodge, by having them move in unconventional paths, or have them follow you or something.
Additionally, it is possible to make enemies take more damage to destroy, or make the player take less damage to destroy. If you're mixing this with other techniques, make sure you don't go overboard, as it is possible to make the game unfair.
The game turned out to be very difficult. To be honest, it turned out a bit more difficult than I had wished, even on the easy difficulty. I made a huge effort to make sure the game was beatable, but I certainly believe I could have made a better job. I am considering making an improved version of the game with more balanced levels.
However, making this game was a huge learning experience for me, which takes us to:
Game 2 (rhythm action game)
Gameplay video: https://www.youtube.com/watch?v=tAYrbmpoS-8
Packed with more experience, my second action game was of a genre with which I am much more comfortable with: rhythm games. I have played pretty much every rhythm game in Japan, and have gotten pretty high in the world rankings of a few of them. Making and balancing this game was much more enjoyable, but certainly not without problems.
The game consists of moving left and right while avoiding getting hit by bullets. The bullets are designed to come out in a way so you can easily avoid them if you move to the rhythm of the music that is being played. If you get hit by a bullet, you die. Lose all lives and it's game over. Live to the end of the song and you move to the next level.
Balancing rhythm games is much easier. Making the rhythm faster as the difficulty increases makes the game more challenging, but not unfairly so.
However, double the speed means at least double the bullets, and quadrupling the speed means four times as many bullets. I also made the more difficult levels have more bullets horizontally, so a hard version of a level has 10~15 times as many bullets as the easy version. We put every single one of those bullets by hand, so making the hard levels took the vast majority of the time to make and test.
So, The faster the rhythm, the closer the bullet pattern has to be to the actual rhythm of the song. Bullets on every second beat are much easier to place that bullets on every half beat. I went to make the game engine support changing the bullet patterns -during- play, which greatly made the level design much more enjoyable than having an external editor.
I really wasn't expecting the hard levels to take so much time to make (about 3 days for just the initial design of one hard stage vs 2 hours for an easy stage), that we had to made some sacrifices in other parts of the game to finish development on time.
But even so, the level design was pretty ambitious. I wanted to have a speed based level, a technical level, a reaction-type level, and I think we pretty much achieved what I wanted. The hard stages ended up pretty hard, but not impossible.
I believe the most critical factor in getting a much better result for the second game was the fact that I play MUCH more rhythm games than action shooting games.
So to sum it up: yes, making hard games is very tough.
I wonder what I'll do for the next action game...