How to prevent false trigger to PIC chip input
I would think it is safe to decrease the pullup value from 20k. for example, connect 1k in parallel.

You mention a spec sheet, but do not say, which one.
It may be the PIC and a value of 20k for an on-chip pullup makes sense.
Still, an external pullup can always be added.

The pullup value is usually not critical.
You only need to ensure that whatever device pulling the line to ground can handle the current.
And that your power envelope can handle it: in battery operated devices we always try to mak all currents as slow as possible.
But in a mains powered device, a 5mA current for the input is probably acceptable.
And your relay contact should easily be able to handle 5mA (5V/1kOhms) instead of the 250 µA you are using now (5V/20k).

You touching the input with a test lead is interpreted as "low"?
This can happen: your test lead (and your body) is an antenna and will pick up all kinds of signals. This will lead to a voltage fed into the input pin.
This could actually overcome the level set by the 20k pullup - although that sounds a bit fishy. I'd guess there was no pullup active at the time when you saw this effect.

Adding a 100nF capacitator to the input is probably also a good idea.
That will eliminate a lot of nasty high-frequency noise picked up by all the leads.
In principle, this will also slow down your inputs response to the external signal (the cap needs to charge up via the pullup before the input is registering as high again), but this will not be a problem in your application: compared to a manual process like "button pressing" the charging process is quick.
But keep it in mind for your next project where you want to de-noise a fast-changing signal. :-)

When reading a relay (or other mechanical contact like a pushbutton) you always need to debounce the signal: the contact will neither close or open instantaniously. It will behave like a rubber ball falling to the floor: it bounces up, falls down again, up again etc. until it finally comes to rest.

Typical bounce times are between 5 to 30 milliseconds in my experience.
Since the code on your Pic is already evaluating a manual pushbutton, chances are good that the relay contact will work right away: if the buttons and relay bounce times are similar, the debouncing routine will already handle it.
If the relay bounce is longer than the debouncing routine compensates for, you need to change the code or find a relay that bounces less.
In my experience, Reed relays show much shorter bounce than mechanicals, at least on average.

Hope this helps
hase