4Mhz is a good standard to start with, but that chip is not limited to 4mhz.
As per the 16F877A datasheet it can use any frequency from DC to 20mhz.
You could use a 32khz watch crystal right up to a 20mhz crystal or even simpler, a resistor and capacitor, if timing is not critical.
See the Oscillator section of the datasheet for all options.
Higher frequencies mean the program inside the PIC runs faster but at the expense of higher current consumption and to some extent the supply voltage is limited. It's entirely up to you which frequency you use, you can even conect a toggle switch to the OSC input and clock it by hand!
This uC can work on various speed up to 20MHz. Examples: 4MHz, 8MHz, 10MHz, 12MHz, 16MHz, 20MHz.
What speed? This depends from Your needs and design of circuit/project. If speed is higher this will cause more power consuption.