Electronic – Switching between USB power and single alkaline battery

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 µ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 µF, so that's not going to change very much, but it gives you some headroom if you want to use a 47 µF cap. AndrejaKo rightly points out that electrolytic capacitors have large tolerances, usually -20 %, and then I would just go for a 68 µF/6.3 V cap.

@AKR: Your suspicion about the body diode is right. Since the drain was higher than the source, the transistor was acting as a diode rather than an open transistor. So, fix #1 was to invert the transistor. In the battery only case, the transistor would initially act as a diode, so Vs = Vd - 0.7, then Vgs < Vth and the transistor turns on, hence preventing the voltage drop. The other fix was to add a Schottky diode to prevent current from flowing back to the gate of the FET.

For folks who are interested, here is the final design:

Thanks for the tip! Moving on to other problems...