Here's another article about Mario-style level design.
And here's an article I came across some time ago while researching procedural level design for platform games. It discusses difficulty and design patterns.
Try to strike a balance between tricky platforming sections and places to "rest." Note that very few platform games are constantly challenging but, instead, provide places to pause and revel in the completion of a difficult section or psych themselves up for the next block. Often, this is done through obvious checkpoints but it doesn't always have to be this discrete.
Remember that in Super Mario Bros, there are bosses even though your primary attack is jumping (fireballs notwithstanding). Bowser can't be defeated by jumping on him but getting past him is a challenge that breaks from the jump-on-everything's-head mold that many simple platformers exhibit. Additionally, Super Meat Boy features several different types of bosses, many with a unique gimmick. But you don't actually attack any of them directly since you can only jump. Not being able to attack doesn't make bosses out of the question; it can actually make them better.