If these rivals were so evil, why didn't David himself punish them? If they weren't so evil, why is it so important for Shlomo to get rid of them?
To answer this question, we must consider the difference between how David and Shlomo rise to power.
David's rise to power began with his popularity as a young and daring warrior who quickly became a national hero (see I Shmuel 18:5-8). Even when he was forced into hiding (after Shaul became jealous), he still enjoyed considerable public support. After Shaul's kingdom faltered, David quickly gained national support and was enthusiastically accepted as king by all twelve tribes.
During his eventful lifetime, David dealt with many enemies who attempted to undermine him. In almost every case, David's approach to these enemies was very passive. He passed up opportunities to kill Shaul (see I Shmuel 24:8-15; 26:4-10), to punish Yoav for killing Avner (II Shmuel 3:38-39), and to punish Shimmi (see II Shmuel 16:5-10). Note that in each of these cases, David's primary argument is his deep faith that God will punish those who deserve to be punished.
Considering that this "midah" is a very good virtue, shouldn't David teach Shlomo to follow his father's example? Why then does he instruct Shlomo to do exactly the opposite?
The answer is quite simple. David was strong enough to allow his opposition to undermine him. They may have caused David trouble, and they were certainly a nuisance, but none of them posed a real threat to David's kingdom. Because these enemies did not pose a threat at the national level, David preferred to leave their personal punishment in God's hands.
Shlomo's situation was quite different, for he was merely a teenager when he became king ("naar v'rach" - see I Divrei HaYamim 22:5 and 29:1). His claim to the throne was nothing more than David's oath to Batsheva (and Natan's prophecy) that Shlomo would become king (see I Melachim chapter 1). Unlike his father, he did not enjoy a strong grassroots political backing. On the contrary, his brother Adoniyahu was far more popular (see again chapter 1), and Yoav remained a very popular general. Aware of this setting, David fully realized that if Shlomo followed his father's passive attitude towards political opponents, his kingdom would quickly fall apart. Therefore, in order to solidify his kingdom, it was critical that Shlomo immediately put down any form of potential rebellion.
Therefore, David's advice to Shlomo is very wise. Because David knows exactly whom Shlomo will have to deal with once he dies, David strongly advises his son to deal with them harshly. Even though David was strong enough to take the passive approach, for Shlomo a more active stand was necessary.
There is a time for pacifism, and there is a time for activism. True wisdom is knowing the proper time for each.