Every one of you GMs has experienced this in the past - when you designed a super awesome big-bad, set up the story perfectly, and the final confrontation awaits. Booming his opening monologue, he sets upon the party...only to get facerolled without so much as a sweat from the party.
- Add Underlings - I cannot stress how useful underlings can be in the equation of an excellent boss fight. Recently I ran an encounter against a second level party, and they faced a Kobold Broodmaster (Summoner) 5. Frail and without excessive hit dice to protect him, the kobold needed a distraction so his eidolons could wreak havok. Merely tossing six first-level kobold warriors (who are almost useless) did the trick - melee fighters attempting to get to him had to deal with pesky kobolds blocking the way, and ravaging eidolons trying to get to their casters. More often than not, underlings provide pathway-blocking obstacles that must be defeated before the boss can be reached, and provide a turn or two extra for the boss to do whatever murderous tactic you have planned for him. Clever use of said minions can even help you divide the party - imagine a boss room with two doors in and a narrow hallway where the PCs start. Simply mob the doorway half the party comes in with underlings, and have the boss assault the second doorway. Party members wishing to help will need to plow through their mess of mooks before being able to join the big fight!
- Environmental Obstacles - A well-designed boss fight should include terrain that is absolutely optimized for your boss. Is he a ranged attacker? Perhaps he starts the fight on top of a cliff that players must ascend via switchbacks. If he's a melee fighter, tight quarters are his friend. Strong enemies do well with terrain hazards they can toss PCs into, and spellcasters work great with walls or doors. Imagine engaging a wizard through an arrow slit!
- Mitigating Abilities and Qualities - I can't stress enough how much damage reduction and spell resistance can help shift your boss fight from "typical" to "challenging". Obscure DRs like x/good and bludgeoning will almost never come up in the PCs vocabulary of threats (and even if they do have the ability to bypass them, they'll end up feeling accomplished for doing so) and help heavily reduce incoming damage from the party. Does your party have a special trick, such as enchantment spells with absurd DCs? Enemies immune or highly resistant to this work well for heightening difficulty and forcing the party to keep on their toes.
- Dominate a Theatre of Combat - In a party that heavily relies on one theatre of combat (melee, ranged, magic, etc) I like to mix things up by making a boss that is significantly better at it than them. Nobody wants to fight the Ogre Mage Lich Monk heel-dropping paralysis effects on them in melee, and if they do insist on trying to slug it out with him they will more than likely end up motionless in a pile on the floor. With these sorts of encounters, it can help to advertise his abilities before the party is forced to deal with them (with friendly mooks, for example) so that an effective strategy can be decided upon before the party is in balls-deep panic mode.