Interesting project.
I would look at the 18F4550 for this and clock it at 48Mhz.

Also a coulpe of threads that may help
http://www.picbasic.co.uk/forum/showthread.php?t=3251
http://www.picbasic.co.uk/forum/showthread.php?t=11571

What do you have in mind for a programmer? The PICKIT2 from microchip is nice...and cheap.