For the capacitors C1 and C2, I suggest anywhere between 22uF and 100uF. The negative side of C1 should be connected to the diodes, and the negative side of C2 to the ground rail. Yes, Vo is the negative feed to the V- pin of the INA125. By supplying a negative voltage to the INA125, the minimum output voltage decreases to (that voltage) + 0.15V typical. So it gets rid of the minimum-output-voltage problem.
If you want to use an external ADC then I suggest the ADS1231. It is 24-bits and specifically designed for bridge sensors. It has a built-in EMI filter and an amplifier with a gain of 128. Its input offset error is only 10uV typical. It comes in a SOIC-16 package, so if you want to use it on breadboard etc. you'll need to mount it on a DIP adapter.