Yes, it must be EDO.
Even FPM I wouldn't attempt, because it has a lower latency - if you mix modules with different latency you should put the slower module in the first bank, so the machine can use all modules at the slower speed.
Because the existing 16mb EDO is onboard, chances are it'll attempt to use the additional memory @ 60ns - which FPM probably wont like too much
Oh, and not to nitpick, but "You cannot mix SDRAM and EDO." is a bit ambiguos, because EDO is SDRAM.
A less confusing statement might be "you cannot mix ordinary PC66/100 memory with EDO"
I'd say the only way the existing additional chip would be anything other than EDO, is if it was proprietry FPM with a lower latency - like many HP omnibook systems use.
Good Luck!