One thing I haven't found in 4th edition online is a plethora of solo monsters. The idea of these fights are fascinating! Sadly though, all the products in 4th focus on multiple opponent fights (with the exceptions of dragons). Are there any tips that you can give me for designing solo fights?
Crowd Control Immunity: By early paragon, a few classes can have stunning encounter attacks, and many have stunning dailies. Solos need to be either outright immune to stun & daze (and possibly blind), or have some easy way to get rid of them (like an at-will interrupt to negate a just-applied effect, or an extra save at the beginning of their turn), or they'll spend the entire fight accomplishing nothing.
Boatloads of Health: Starting in early to mid paragon, and earlier with lucky rolls, properly built strikers can take out an elite with an encounter nova, and seriously wound or even straight up kill a solo built by the normal guidelines. Consider giving it 1.5 times the recommended HP, or even simply ignoring HP, and allowing the monster to die only after at least 2-3 turns of being pounded on. Since multi-attacking is the primary means strikers use to achieve quick kills, consider giving the solo an at-will free action ability that pushes away attackers or even blinds them until the start of the solo's next turn; this makes it harder for players to unload 3+ attacks in a single round.
Multiple Actions: A solo counts as 5 normal monsters; that means it needs to rival 5 normal monsters for damage output. Every solo should have at least one of the following at-will, if not more: two standard actions per round, a good 1/round minor action attack, a standard action ability that allows the solo to make 2-3 basic attacks.
Multiple Phases: Instead of giving the solo giant piles of health, give it multiple phases: after the party defeats the powerful necromancer, his spirit possesses the skeleton of a dragon, and when the party defeats that, they then have to defeat the spirit directly. Each phase should have its own hit point total (though each phase should always survive long enough to take at least 1 turn; ignore HP if necessary) and its own set of abilities. World of Warcraft is a good source for multi-phase boss fight examples.
An Exciting Environment: Combat in 4e should never take place on a feature-less plain or in a boring square room, and that goes triple for boss fights. Put in lots of interesting features. Dragon eggs that hatch if the party gets too near them, fire coming out of the ground in elaborate patterns, ground falling away forcing the party to leap from rock to rock, and so on. Again, WoW is a good source of examples (look up a video of a raid doing the Safety Dance). The solo will usually be immune to the hazards in its area.
Monster Manual 3: After a while the designers realized one of the reasons 4e sometimes turned into long slugfests was that monsters had a bit too much health and didn't do quite enough damage. This was corrected in MM3, so try use MM3 solos as examples rather than solos from MM1 or 2. The Dark Sun Creature Catalog, Plane Below, both Monster Vaults, and the Shadowfell box are also post-MM3 and use MM3 creature balancing (thanks Simon!).
Clarification: The MM3 part may appear to conflict with the Boatloads of Health part, but this isn't actually the case. The goal is to create a fight that lasts 2-5 rounds and consumes at least 1 daily power and 1 healing surge per player (though not necessarily evenly distributed between the party). If you can judge your party's damage output well enough to achieve this lifespan by setting the solo's HP total ahead of time, more power to you. If not, then consider not tracking HP and simply pretending they've finally done enough damage once you feel the fight has gone on the right amount of time.
Additional Stuff: As BESW mentioned, the Angry DM wrote a great series of articles on improving solo fights (part 1, part 2, part 3, part 4). In particular, it's an excellent resource for learning more about building multi-phase fights (it includes two examples).
Sid Meier said something along the lines that a good game is a series of interesting decisions. Thus, the key to making fun Solo monster fights is to present the players with an array of tactical choices to make during the fight.
Traditional fights move multiple monsters around to give players basic tactical choices: where to move, which target to attack. Solo monsters tend* not to move as much and not to present players with as many targets (*when played as presented in some of the earlier material). Thus the trick to making good Solo fights is to find other tactical choices for players to puzzle over on their turns.
It can be helpful to look at modern boss battle design in video games for inspiration. Games designed for large groups, such as MMORPGs, often have to find ways to keep every player interested and engaged in the battle even if they're not the one being attacked.
Exciting Environment: It isn't sufficient to simply design an interesting battlefield because that will only provide interesting choices for the first few rounds. Once everyone is settled into an optimal location, movement will come to an end and the fight will grind on as a war of attrition until the bosses HP pool is finally exhausted. Therefore, it is important to have a continuously changing environment. Fights with multiple monsters continuously change as monsters move around; with solos, you'll want other features to move around and change the environment instead.
For example, the Blue Dragon Broodmother in the final installment of the Scales of War campaign (Dungeon 175 p.41) keeps the battlefield changing by launching randomly moving whirlwinds down various paths, flinging players to and fro. Players have to try to guess where the whirlwinds are going and how to get out of their way.
You can also turn to the tried and true MMORRPG method of lobbing attacks at random places around the battlefield to keep players moving. You can designate several target zones on one turn, then have attacks hit them on the next turn. It might not be fun in a time-sensitive way, but you can carefully place them to block off all the good spots and force players to find other squares to stand for a round.
You can also make the battlefield more fun by having the battlefield move around. Imagine a battlefield of floating platforms moving to different locations each round. An advantageous spot at one moment might put someone up close to the boss the next! You can also keep the battlefield moving in other ways, like having the players fight a boss while in a tunnel that's collapsing, yipes!
Multiple Actions: While having a lot of actions sounds good in theory, it's horrible in practice, especially if the Solo executes them all on its one turn. The last thing players want is to get hit with a "nova" attack that knocks them out before they can react. A better idea is to give the Solo monster several turns in the combat order, to spread out the damage and give at least a few players a chance to react between attacks.
For example, Tiamat (Dungeon 175 p.46) is a famous 5-headed dragon and, appropriately, gets 5 turns on 5 different initiative spots. This, in a sense, makes the fight feel more like fighting 5 monsters instead of 1 (which, as you point out, is what a lot of D&D combat is based around) and keeps the battle a bit more interesting because you don't have a full cycle of player actions between monster attacks. (Mind you, Tiamat is also poorly constructed and the designers forgot to give her move actions, oops!)
Alternatively, you can give the monster more off-turn actions, such as opportunity actions and immediate actions that have different triggers. I'd even be willing to fudge a Solo and give it 2 or 3 Immediate actions per round rather than just one, to keep things exciting! Rely on off-turn surprises to ambush your players more than on-turn novas. (Again, Tiamat gets 5 immediate actions per round, refreshing after each head's action)
Find ways to allow players to counter additional attacks. For example, a standard action that grabs a player, then a minor that does damage to them on subsequent rounds, is a common trick used in the Monster Manual books. This sort of says "you've got one round to get free or get freed or you'll get pwnd!" and gives the players an additional objective to work towards. This is especially useful if there are non-obvious ways to avoid the extra damage, like intentionally falling prone to avoid a scything blade that careens over the battlefield.
Immunities: I think the default ruling of +5 saving throws is a horrible way of dealing with the disability problems, especially because they blanket affect things that Solos certainly don't need special immunity from, like ongoing damage (especially with those 1,000+ HP pools!). Instead, find creative ways to limit crippling effects. The creature is knocked prone, but stands up after being hit once. Dazed cripples one of the dragon's claws, reducing it's claw claw bite attack to just claw bite. Dominated allows you to force it to miss one opportunity action or immediate action it declares per round.
(Tiamat counters stun and dazed by having it affect only the next head to take its turn)
Ultimately, I'd take a LOT of liberty dealing with status effects on a Solo monster. You're the DM, you can make stuff up on the fly. It's useful to evaluate how crippling each effect is and how much of a benefit it gives the party. If your entire party relies on knocking monsters prone and wailing on them with Headsman's Chop, you might allow your monster to stay prone for the feat but retain movement capabilities or not grant combat advantage. You have to be careful not to completely negate your party's well thought out and coordinated strategy by simply making the monster immune to it, but you are more than welcome to give the players an added challenge for the Solo fight (so, in this example, standing up after being chopped once gives a balance between some chopping and not too much chopping).
Extra Objectives: I've often seen skill challenges wrapped up with Solo monster fights to give players an extra set of tactical options. You could fight normally... or you could try to fiddle with that arcane blaster tower over there that could drastically sway the tide of battle. Be careful with skill challenge designs though, you don't want to simply negate one player from the party by having the challenge only use their skill, like a trap that only takes Thievery checks which basically takes the Rogue out of the fight and forces her to do nothing but skill checks each round.
A good idea is to have the Solo monster interacting with the skill challenge too. Perhaps the arcane blaster has several control panels and the Solo is actively trying to keep players away from all of them. By splitting up and running to different ones the Solo can't stop them all, and by using good forced movement and controller powers the Solo might not be able to intercept a player making a mad dash under its legs to reach the final panel. This kind of coordination is both fun and cinematic!
Random Powers/Status Effects: Another way to keep players engaged while fighting a Solo is to employ the randomness of dice rolls. You can re-create things like WoW's famous Heigan dance by marking different coloured areas on the floor and afflicting people with a "dance (save ends)" penalty. At the start of each turn, they roll a die equal to the number of areas on the floor, then if they don't end up in the area corresponding to the die they take damage/penalty/something. Roll a die and determine your fate... OH NO! That's the furthest one away! How will I ever get there in time?
In closing, I'd suggest being very creative with Solo monsters. The creativity of encounters largely comes from terrain and monster composition, but Solo monsters really stand out. They tend to have interesting stories and personalities and tend to be more meaningful than just a wave of orcs. They should be exciting boss fight moments that really push players to their limits -- both power-wise and to the creative edges of role-playing.