Not really sure exactly how quickly the avr responds to an interrupt.
Pretty fast, the order of events is something like this
int happens (a pin change int takes 4 clock cycle to be recognised)
wait for end of current instruction
push current program counter onto stack
load int vector into PC
IIRC I've seen it take about 1.5uS to get into the ISR.
Thats at the ASM level, however if using C there could be a stack of extra code to save registors as well.
Just as an aside, it can be faster to poll, if you really need to react fast to say a pin change it will be faster to just constantly read the pin. Of course you don't get anything else done