The conventional wisdom would say anything greater than 50W. There are two complications though: one, the amplifier rating may be exaggerated by the manufacturer and two, it's best to have plenty of headroom in the speaker so the amplifier can never damage it.
Speakers are sometimes overrated by their manufacturers as well, so for efficient power handling without distortion my advice would be to use a speaker rated for 100W.
4 Ohm is the minimum recommended impedance, there's no need to put 2 8 Ohm speakers in parallel.
Almost all amplifiers in the range of 10 to 100 watts are comfortable with a 50 watt speaker but you shouldn't overdrive an amplifier because that's when the output gets dirty and dangerous. If you have to turn an amplifier above halfway on the volume, then you really need a bigger better amplifier.
Other problem is, that the amp is usually capable of putting say 100W into 4ohm load, but it will probably achieve less than 50W into 8ohm, so paralleling the speakers is not a bad idea. I usually like to use the lowest recommended impedance available.