Connecting more than one serial device to PIC16f877a

I've not used the Arduino, but have written efficient soft UARTs on quite a number of platforms. Which approach is best on a given platform will depend upon what types of bit-munging operations it can perform most efficiently. I would offer a few suggestions, though:

1. Assign maximum priority to the serial-polling ISR, and run it at preferably 3x the desired data rate. Sample all your inputs and write all your outputs at the start of this interrupt routine, and then figure out what the outputs should be for the next pass. This will help to minimize any timing skew that might otherwise be caused by variable interrupt processing time.
2. For the receiver, instead of using a state machine as such, it may be helpful to effectively shift the incoming data into a big shift register. If the pattern of bits indicates a byte was received, grab the data and clear the appropriate bytes.

     ... near start of interrupt (for consistent timing)
     shiftreg >>= 1;
     if (IN_PORT)
       shiftreg |= 0x20000000;
     ... other interrupt logic, then...
     if ((shiftreg & 0x20000007) == 0x20000001)
     {
       int result = 0;
       if (shiftreg & 0000000040) result |= 1;  // Note: constants are OCTAL!
       if (shiftreg & 0000000400) result |= 2;
       if (shiftreg & 0000004000) result |= 4;
       if (shiftreg & 0000040000) result |= 8;
       if (shiftreg & 0000400000) result |= 16;
       if (shiftreg & 0004000000) result |= 32;
       if (shiftreg & 0040000000) result |= 64;
       if (shiftreg & 0400000000) result |= 128;
       // Do something appropriate with result, then...
       shiftreg |= 0x3FFFFFFFF;
     }
     else if (shiftreg = 1)
     {
       ... Do something with long-break (will be detected exactly once)
     }
   

Note that while the worst-case time may be significant, the normal-case time will be quite fast. Further, when an incoming byte is detected, one could copy it to another word of memory and do the bit-munging on a later interrupt. Since serial-transmit will only need to do something every third interrupt, the bit-munging could be done on interrupts where the serial-transmit routine doesn't run.

Another answer: Stop using interrupts.

People jump to use interrupts too easily. Personally, I rarely use them because they actually waste a lot of time, as you are discovering.

It's often possible to write a main loop which polls everything so rapidly that's it's latency is within spec, and very little time is wasted.

loop
{
    if (serial_bit_ready)
    {
        // shift serial bit into a byte
    }

    if (serial_byte_ready)
    {
        // decode serial data
    }

    if (enough_serial_bytes_available)
    {
        // more decoding
    }        

    if (usb_queue_not_empty)
    {
        // handle USB data
    }        
}

There might be some things in the loop which happen far more often than others. Perhaps the incoming bits for example, in which case, add more of those tests, so that more of the processor is dedicated to that task.

loop
{
    if (serial_bit_ready)
    {
        // shift serial bit into a byte
    }

    if (serial_byte_ready)
    {
        // decode serial data
    }

    if (serial_bit_ready)
    {
        // shift serial bit into a byte
    }

    if (enough_serial_bytes_available)
    {
        // more decoding
    }        

    if (serial_bit_ready)
    {
        // shift serial bit into a byte
    }

    if (usb_queue_not_empty)
    {
        // handle USB data
    }        
}

There might be some events for which the latency of this approach is too high. For example, you might need a very accurately timed event. In which case, have that event on interrupt, and have everything else in the loop.