Hello

Transmitter and receiver do not need to operate at the same speed. They only have to use same baud rate. For instance, PIC and PC work at very different speeds yet they can communicate.

As regards need for 20MHz oscillator for serial communication, I don't think that's correct. 4MHz is perfectly enough as long as you utilize adequate baud rates. Since it is a software serial communication, I would recommend not to exceed 2400 baud.

Send some garbage first to "clear" comm-line and then transmit real data.

It is good practice to apply pulling resistors, pull-downs in your case since you're using inverted mode.
Also make sure that data line is not too long.