Serial driver for full 3.3v uC to back-of-computer

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.

I'm not an Arduino user myself, but from what I read here all the time it seems that it works on 5V.

Confirmed here, see also this lousy schematic.

You need the 5V display.