PIC16F877, like all the other 28/40 pin PIC pkgs I know, have only 2 hardware PWMs. You will have to hack something together for the 3rd color. Fortunately, the rate doesn't have to be too high so the software solutions aren't too bad.
PIC16F877 is obsoleted by PIC16F877a, BTW. And the "a" is cheaper now.
Your pkg is a bit of overkill... 28 pin ones are easier to build with. But yes, it'll work fine.
The current listed on the LED specs is near the absolute max (not continuous) of 25mA for a PIC pin. Common anode would be better since the pulldown capabilities are a bit better than pullup. Take into account that the PIC pin output voltage will not be 0V when low, but will get pulled up to 1V or so under the heavy current. This will strongly affect your resistor sizes. Still, the best thing to do is add 3 external transistors to drive it.