I'd get the 470uF 35V since it's the same price as the 25V. While you are operating at 12V DC in THIS application, the 35V rating is useful for general O-gauge applications so why not "stock" something you might be able to use later. I have to throw in that if you "do" eBay, you can get the same for less than 10 cents each.
Choosing capacitor size 330uF, 470uF, etc. can get into some nerdy math. I'll throw out some back-of-the-envelope numbers showing the relevant relationships. Use them, study them, ignore them, laugh, cry, up to you!
The capacitor provides anti-chatter protection which keeps the relay closed during brief interruptions of the 12V relay control signal due to dirty track, wheels, rollers, etc.. The capacitor gets instantly charged up to 12V DC when the wheel axle "shorts" the outer rails. During the interruptions, the charged capacitor provides 12V DC to hold the relay closed until 12V is restored. The larger the capacitor, the longer the hold time. Per the datasheet for your chosen relay, it will stay closed as long as the relay voltage stays above 9.6V DC; that's just a worst-case spec and relays will stay closed at much lower voltages but you need something to start with. Next, for your specific relay with a 135 ohm coil, the current drawn when active is 12V / 135 ohms = 0.09 Amps (90 mA). How fast does a capacitor drop in voltage when dumping 0.09 Amps? More math. A 470uF capacitor dumping 0.09 Amps drops its voltage at a rate of 0.09 Amps/470uF = 200 Volts/sec. So if starting from 12V, it will drop down to 9.6V in only 0.01 sec. IMO this is on the hairy-edge but it is a your-mileage-may-vary situation and may be just fine. Maybe you get an occasional red-green flicker on the signal light but so what?!
You can fiddle with the numbers. So suppose you got the 160 ohm coil relay version you mention. Plugging in 160 ohms instead of 135 ohms the hold time increases about 20%...or up to 0.012 sec instead of 0.01 sec. No cigar...so why bother. But go to a relay with 3x the coil resistance as GRJ suggests and you triple the hold-time and now we're talking turkey.
I understand the conceptual simplicity of just using a double-pole relay with one pole for the lights. OTOH there is something curious about using a 10 Amp relay to toggle between Red and Green LEDs that draw about 10 mA (0.01 Amps) or 1000 times less current than the relay can handle!