I went with a P16F1827
Has enough pins to do what I want. I also have MPLAB and a PICKIT3.
Now to just figure out a simple code to make the 2x16 LCD say "Hello" in 4 bit mode.