Use a pic 18Fxxxx like 18F2585 for instance, with a 40 Mhz xtal oscillator.

Here the setting for the EUSART @ 115200,n,8,2 (Obtained with Mister E PicMulticalc)

Code:
RCSTA = $90   ' Enable serial port & continuous receive
TXSTA = $24   ' Enable transmit, BRGH = 1
SPBRG = 86    ' 115200 Baud @ 40MHz, -0,22%
SPBRGH = 0
BAUDCON.3 = 1 ' Enable 16 bit baudrate generator
Al.