Basically all you are wanting is a sequencer, the only problem is the large number of outputs you want - there are a number of ways you could do this.
You could use any PIC, and expand it's output pins using serial to parallel TTL converter chips - often called 'port expanders'.
Or, you could use multiple PIC's, and link them together.
Suggestions of 'top of the range' PIC's are pretty pointless, it's a VERY! low spec project - a 'clockwork PIC' could do it :lol:
Personally, I'd go for the multiple PIC option, using one PIC as master (generating the patterns), and other PIC's as slaves - with them all linked via serial connections, in on one pin, and out on another to the next PIC. You can simple stack as many together as you need, and add more at a later date if required.
If you used 16F628's, these have 16 I/O pins, so allocating two for serial I/O leaves 14 available for driving your outputs. If you use a 16F877, which has 33 I/O pins, this potentially leaves 31 for your ouputs.
Again, personally, I'd probably go for the 16F628, the chips are cheap and they don't need an external oscillator - so it makes each PIC board extremely simple.