Yeah...
you don't need 2 phones but sometimes 2 SIM cards.
Optus has greatly improved their 3G coverage in the bush, but not near Telstra's Next G standard. To access Optus coverage cheaper sign up to Virgin Mobile, which is a wholly owned subsidiary nowadays.
I don't think that 3 roams onto Telstra 3G, only Telstra 2G, otherwise it would be the cheap way to take advantage of Telstra's coverage without their impressive bills. Tel 2G cover ain't that flash.
Make sure you have a a handset that is "dual band 3G" but quad band would be better.
Here's the technical bit: Quad band phones work on 850, 900, 1900 and 2100 MHz. Within Australia you can disregard the 1900. 2100 will work best in built up urban environments but the lower freqs will work over a greater range. Telstra Next G uses 850 and other Aus 3G networks use 900. If your handset doesn't do one of the freqs, you are out of luck in an area that only has it, even for emergency calls.
Get the right handset, make sure it's not locked to any network, get your first choice of network on a plan that suits you and take a Telstra Next G pre paid SIM with you for the other times.