The 8Mhz internal oscillator in most 18F PICs will work fine with SEROUT/SEROUT2 at up to 9600 baud. If you use DEBUGOUT, you can extend that to at least 19.2Kbaud.

Amazingly enough, I have used the 8MHz internal oscillator on an 18F2221 to communicate with another PIC at 38.4Kbaud (using DEBUGOUT). This worked across 16 parts, and all were tested to be fully operational while running in a temperature chamber -20C to +85C.

And as far as whether to use a MAX232 or not - the level coming out of a PIC does not meet RS-232 specs. While it usually works, I would never sell a product that way.