I'd use one of the following chips... 18F1220,18F1230,18F1320,18F1330. (the difference between these is programs space and 4 vs 2 timers).

Why, you ask? For starters..
- Cost wise they look about the same, maybe cheaper than the 16F84 (just from looking a Microchips Web site), and its pin compatible (MCLR, Vss, Vdd, OSC pins are the same).
- They have harware Serial (USART) built in, allowing an interrupts or polling of the RX bit (more on this later, as it is the most valuable IMO).
- It can run at a faster clock if needed to keep up with tasks and speed up the baud rate if needed
- It has more memory available
- It has more timers
- It has an expanded instruction set (although this is likely transparent when using PBP)
- And other minor things...

Once I had this chip, I would use the built in hardware USART and either ...
1) use Darrel Taylor's Instant Interrupts or
2) Poll the RX bit flag a periodic intervals (based on buad rate and the tasks the uP is working).
Either of these would allow for monitoring the serail comm "in the background" while the uP is accomplishing it's timing and control of the relays and other stuff.
The timers can be set up to keep track of the duration of no serial activity, time changes in the relays, etc.

Based on you rough outline, my basic plan of attack would be:
- Get a heart beat (flash an led to make sure all is well with proto setup)
- (I may set up a serail lcd to help in debugging/development if I had a spare pin and lcd)
- Set up the basic USART and get comm working
- Set up the USART interrupt/polling to catch the comm while blinking led
- Set up the Timers for accureate timing
- Finish of logic for relays to get them switching at the right times

HTH,
SteveB