With a 10bit ADC (like most PICs have) and a VRef of 5V you get a (theoretical) resolution of 4.88mV. Your typical sin/cos type encoder outputs 1Vpp which means that (again, in theory) you should be able to "divide" that signal into approximately 200 "steps".

If yours is actually 1.5Vpp then that's obviously "better", you'd get 300 "steps".

At this stage I would not bother trying to amplify and/or offset the signal(s). I'd concentrate on seeing if it's at all possible to begin with. Then, if it does work but needs more resolution I'd start looking into what can be done either with the signals themselves or with, for example, the reference voltages for the ADC.

The thing is that even if the PIC has 10 analog channels there's only one ADC and (usually) one S/H circuit. This means that you have to sample and digitize your two signals in sequence which in turn means that cos will change while you're digitizing sin (if the encoder is rotating). With dual S/H circuits (like in the 18F2431) you'll be able to take a snapshot of both signals at the same time, then convert them in sequence because there's still only one ADC.

Again, this MIGHT not make a difference in your case - or it will totaly ruin it - I don't know but you need to be aware of it.