Voltage should be pretty much irrelevant for an input capacitor unless your source has a massive DC offset. Making it a bit higher than the supply seems a reasonable start - the original may well be specified as 100v just because that's one of the more common voltage ranges for that type of capacitor - metallised polyester don't seem to go below 50v and 100v is more common than 63v which is the lowest common voltage in farnells list.

Definitely don't use an electrolytic. The article you linked to describes the choices pretty well - basically work out the value for the amount of bass attenuation you can live with and then go down the quality levels until you find something that will fit at an acceptable price.