USB / Battery Switchover Circuit
No, like you already may have feared this isn't kosher. The 3 V is indeed the minimum, and the AA batteries' voltage will quickly drop below that. If you're using NiMH rechargeables you even get only 2.4 V, so that won't do, unless you can use 3 of them in series. (Don't use batteries in parallel like you mention in your question.) So three NiMH cells will give you 3.6 V. Fine.

That 3.6 V is the maximum VDD for the device, so if you want to run it off USB power you'll need an LDO (Low Drop-Out) voltage regulator to get 3.6 V. The LP2981 is a good part for this.  

Now the switching. 175 &micro;s seems like an eternity to me, but we'll have to live with that. Ben gave you already the right equation for a constant current discharge:  

\$ \Delta V = \dfrac{I \cdot \Delta t}{C} \$  

or 

\$ C = \dfrac{I \cdot \Delta t}{\Delta V} \$ 

NiMH cells have a fairly constant 1.2 V, which only drop to below 1.1 V when they're nearly discharged. 



So we can use that as a limit. With a minimum voltage of 3 V and a worst-case current of 70 mA you get

\$ C = \dfrac{70 mA \cdot 175 \mu s}{300 mV} = 41 \mu F \$

which is what Ben also found. If you think you won't go below 1.15 V then that would become 27  &micro;F, so that's not going to change very much, but it gives you some headroom if you want to use a 47 &micro;F cap. AndrejaKo rightly points out that electrolytic capacitors have large tolerances, usually -20 %, and then I would just go for a 68 &micro;F/6.3 V cap.