Instruction cycle = oscillator/4, i.e. 20Mhz oscillator = 5Mhz instruction cycle rate = 200ns per instruction cycle. Most things in a PIC are based off the instruction cycle, not the actual oscillator.
Yes, 20Mhz is more than plenty.
Spare instruction cycles - best to handle as much as you can in the main loop. Get in and out of the interrupt handler as fast as possible. While you are in the interrupt handler, you generally can't handle another interrupt (well, you can, but that's beyond the scope at the moment), therefore, you can't handle anything else until you get out of that interrupt routine.
Instruction cycle - a NOP takes one instruction cycle, it also takes one word of code space.
A GOTO takes 2 instruction cycles, but takes up only one word of code space. That info is in the 'Instruction Set' section of your PICs datasheet.
But to figure out how long it takes each 'block' to execute, you either have to count it out, or use one of a few different methods to calculate it (MPLAB, use one of the PICs timers, etc.etc.).