Here's how I calculate hold up. Start with an equation that determines energy in terms of voltage and capacitance. Then solve for C.

E = (1/2 C * Vstart^2 - 1/2 C * Vdropout^2)

For the algebra challenged, here's the steps broken down to solve for C.
1. Take your circuit's current times the circuit's voltage, to get Power (then double it)
P = 2x (Voltage * Current)

Calculate energy required by multiplying power by time.
E = Power x HoldUpTime

Calculate the V^2
Vrange = Vstart^2 - Vdropout^2

Solve for C.
C = E / Vrange

An Arduino board by itself draws 30-40mA depending on which regulator, so assume 50mA for margin. The ATmega328 chip is only rated to 4V (or so) at 16MHz.

P = 5V * 50mA = 250mW * 2 = 500mW
This is an extreme estimate.

E = 500mW * 500mS = 250mJ
Time is 500mS (or recalculate for 100mS)

Vrange = 5^2 - 4^2 = 9V
The 4v dropout is probably higher than it really is, so you get some additional margin.

C = 250mJ / 9V = 0.02777 F
So thats 27mF or 27,778uF.

I'd probably round up to a 33,000 or 47,000uF. However, the whole calculation has lots of margins built into it, so its your call.

No need for a Supercapacitor/EDLC. You can get away with a regular aluminum electrolytic. Not critical, but try to get the lowest ESR you can.