Usando esos 2 micros, la velocidad del programa si usas un oscilador de 4MHZ en ambos deberia ser practicamente igual.
Tengamos en cuenta tambien, que habria que ver el codigo ASM que genera el compilador para cada micro.
Suponiendo que el codigo ASM es identico para ambos micros:
Si estas conectando esto a una PC con un programa que envia los valores, y lo probas en dos PC distintas, te aseguro que ninguna PC es igual a otra, ya partiendo de cosas tan detallistas como la cantidad de particulas de polvo dentro del microprocesador a la hora de su fabricacion, como las cargas de tareas en ambas, etc.
Entonces, si tu sistema funciona de la siguiente manera:
PC envia DATO. Microcontrolador responde, PC envia otro dato, Microcontrolador responde...
seguro vas a notar variaciones en la velocidad de procesado, aunque realmente a la diferencia significativa la hace el cambio de PC, y no el uso de un 16F877A o un 16F628 funcionando ambos a 4Mhz.
Saludos.