Higher values polystyrene is the best but is no longer made.
I happened to notice on eBay the other day these beauties from Russia:
http://www.ebay.com/itm/Polystyrene-Capacitor-K71-4B-71-4-10-0uF-160V-2-1pc-or-more-/380791403351?pt=Vintage_Electronics_R2&hash=item58a8efb357
One problem you may find with high values of Polystyrene caps is high inductance,due to their construction.
Back in 1974,as part of modifications of an old Marconi TV Transmitter for PAL colour use,we replaced the 0.47uF Metallised Paper coupling caps in the "Sub-modulator"(which were looking a bit worse for wear),with nice new Polystyrenes.
When we swept the modified device,we were horrified,as the frequency response was "fish-shaped".
We re-fitted the old caps & all was OK,tried the new ones,& the "fish". was back!

We couldn't find anything else in the voltage & capacitance rating,other than waxed paper,so we used those.
Musn't have been too bad---lasted around 20 years!
I've seen plenty of polystyrenes used in HF circuitry since then,but always lower values.
Maybe there is a change in construction with the higher values which causes the above problems.
I have noticed that the large values are usually bigger physically than equivalent values using other dielectrics---the Russki ones look quite large,too!