Here's the types of penalties I can think of:
- Destroy the player's progress/time. (Mario setting you back to the beginning of the level when you die, and to the beginning of the game when you game over.)
- Destroy something the player has accumulated. (In Starcraft, your buildings being destroyed. In Sonic, losing rings.)
- Remove an opportunity from the player. (In Farmville, you have the opportunity to reap your crops during a certain time period, but if too much time passes then the crops rot. Nothing is taken away from you, but the opportunity to accumulate gain is lost.)
- Reduce the player's autonomy (reduce the number of things he can do; losing your fire power in Mario when injured is a penalty... or in Limbo, being "possessed" takes away control of your character, which feels like a penalty to the player).
- Reduce the responsiveness of the game (make the controls sluggish, e.g. "Touch Fuzzy Get Dizzy" in Yoshi's Island... or, being blinded by a flashbang in Counter-Strike, which removes ALL audio/visual feedback temporarily).
I'd also be interested in experimenting with the idea of increasing OR reducing challenge, as a penalty - however this is a weird and recursive idea, since usually the "penalty" in question is meant as a "consequence of failure", the failure being that of not conquering the challenge in question.
Trial-and-error gameplay can actually be the least punishing type of gameplay. Super Meat Boy is one of the least punishing games ever made. The only "punishment" ever inflicted on the player is that of losing progress; but
- 1) the progress is always less than 30 seconds' worth, and
- 2) this progress is NEVER lost due to factors outside the player's control (there's no randomness in the game, everything is deterministic).
A truly punishing game is NetHack, or an old-school MMO featuring permadeath: one where the player can easily lose hours of progress due to circumstances that they had absolutely no control over - a failure that they couldn't have prevented. Even when a failure is PERCEIVED as being one that couldn't be prevented, the player feels frustrated - this type of "penalty", one that is feels like an undeserved punishment, is particularly harsh and frustrating, and each time one happens, you have a large chance of your player quitting!
Of course, your player will never "like" any of the penalties I described, which is why they're penalties - they're undesirable! But it's impossible to make a game that features challenge without including failure of some kind, so it's up to you to decide what form that failure takes. Note that more mainstream successful games feature less harsh penalties. (Again, it's impossible to ever lose anything in Farmville, actions either give you a reward or no result at all... it's only possible to lose an opportunity to gain something new. Though that kinda equates to the same thing as losing something, it's not perceived that way for the player.)