go for a 40 pin device then. PIC16F886, 16F877(a), PIC18F452, PIC18F4520 etc etc

if you have a serial port, try to build your own JDM programmer, lots of info all 'round the web. Make sure the software for the JDM will support the PIC you'll choose.