Brutes And Soldiers slow down combat
A Brute or a Soldier is fine, but more than 1 of either is simply going to drag combat out. Soldiers tend to have very high defenses meaning the party will miss more often. Brutes have a lot of health which will take awhile to drill down. Both Brutes and Soldiers often have useful forced movement abilities, but these are almost always encounter powers that don't recharge.
I will always remember an encounter that occurred during my first 4e campaign in which our DM used not 1, not 2, but 4 brutes to make up the enemy party. It took over almost an hour and a half for a party of 5 to take out 4 level appropriate enemies (and the combat was the most boring type imaginable).
Utilize Leaders with minions, artillery, skirmishers, lurkers and controllers
All of these monster types tend to create more dynamic fights. Lurkers and skirmishers are melee combatants that move around a bunch themselves, forcing players to move as well while also giving a defender some nice punishment provoking to make them feel useful. Leaders can take those waves of minions you've used and really spice them up and make them temporarily more powerful than they were before. Artillery units can hang back behind everyone else acting as glass cannons forcing the PCs to try to rush them. Controllers can seriously change the layout of combat much as a PC Controller class would.
There is no magic formula to use every time
I can't give you a template, such as 1 leader, 5 minions, a soldier, an artillery, and a controller, and say that it will work every time. Even if it did, by the very nature of repetition it would become boring and stale for your players. The beauty of the XP balancing system in 4e is that you can mix things up and still make a balanced encounter (provided you use monsters within 1 level of the party level: -1, same or +1). There could be an artillery heavy ambush or multiple leaders ordering around lots of minions and it would work just as much as the above formula I just gave you.
Mix up the combats by adding dangers to the arena/dungeon in which they occur
Traps in general are a good tool, but adding traps and environmental dangers that are equally dangerous to monsters and PCs alike will make for some really interesting combat encounters that will leave your players with fond memories. Additionally, adding a 3rd group or single powerful monster that is also out for themselves can be really entertaining. That fight between the PCs and the goblins in the cave could be really spiced up when a wandering owlbear just happens to stumble in and indiscriminately start attacking both groups.
Create Solos that act and behave like the boss monsters they are meant to be
Solo monsters can be either incredibly dangerous and nailbitting or incredibly boring with very little room in the middle for both interesting and challenging without being a TPK. Solos fit in a weird niche in that they have the XP value of a whole encounter so they need to be tough enough to last awhile without being so tough that the Party is dropped. Quite often solo fights are too easy from focus fire (whole party dumps all their dailies on 1 target) or too hard because to counter being focused their higher defenses, ability to shrug off conditions, and big health pool make them too difficult for PCs to take down fast enough.
The Angry GM has an excellent series of posts (Parts: 1, 2, 3, 4) detailing all of these issues and his proposed solutions (which I totally agree with). I've summed some of them up below, but be sure to check out what he's written.
Solutions:
- Solos act on multiple initiatives. Create solos that have 2 or 3 initiatives during which they can do 1 or 2 specific types of actions, but not a whole turn. Suddenly Solos can interact with the party throughout a round rather than having 1 big solo turn than the rest of the party and so on. Giving each initiative roll different modifiers (+5,+10, +15) will help to ensure they are staggered or just giving fixed initiative values such as 10, 15, 20).
- Solos are made up of different "parts." Take those different initiatives you've built in and they literally correspond to different parts of the solo monster. For the example you gave the dragon's tail, claws and head would each be a part of the monster. The head would have the best Defenses and HP because if it went first the boss would essentially be defeated, but players could destroy the tail or legs in the fight costing the monster those abilities and the initiatives linked with them.
- Solo monsters have "stages." Solo monsters transform as they are defeated throughout the fight. That wizard the party fought takes an immediate reaction when his HP hits bloodied, transforming into an abomination by drinking a potion/uttering a spell. Where he was a wizened wizard throwing spells before, now he is an 8 foot tall hulking mass of muscles and horns seeking to smash the party.
Create recurring villains that also fight in encounters†
Creating a powerful Leader or artillery type monster stat block for a recurring villain can be another way to spice up the combat and add further weight to an encounter.
†Absolutely no guarantee that your players won't cut him down in the first encounter. The ways around this are to have a valid escape route with plenty of enemies in-between him and them which he flees down and then triggers a trap/lock behind him allowing him to escape. Also, giving him a teleport power to rapidly escape is another option.