I travel and work in rural New South Wales and Victoria, and I've been testing several NextG phones in some pretty remote areas.
I recently downloaded the bsdtalk MP3 at 200 kbps while I was doing 100 km/h with the nearest tower barely visible over the horizon.
Telstra's data might seem a little expensive at first, but I recently stayed in a motel in Sydney where the price of wifi access was $30/day.
The ZTE phones are only available through Telstra, with (excessive) Telstra branding. They are relatively cheap and work reasonably well as a modem, but I don't think they are good value for money. I have tested this with the ZTE-252 flip-phone, and the ZTE-158 "ruggedized" handset.
Apply this kernel patch (against 4.1-current, just prior to the 4.2 release). This will let you use the ZTE phones as a modem, I would expect other Qualcomm-based phones would also work.
Use this ppp.conf file, connect by typing "sudo ppp -ddial nextg1"
The ZTE phones are rated at 3.6 Mbps. In over a month of testing I never got over 800 kbps, but rarely got under 600 kbps even in remote areas.
Note that I no longer have access to any ZTE phones, so if you have problems you are on your own.
The LG TU-550 flip phone works with the same patch and ppp.conf as the ZTE above.
The LG TU-550 phones are rated at 1.8 Mbps, I usually get around 600 kbps. Note that the USB data cable supplied with the LG does NOT charge the phone, so this is not really suitable for heavy use. I have used this phone via bluetooth using WinXP, so maybe one day...
If you have another brand of phone you would like to get working with OpenBSD please contact me by email. I have access to a few other Samsung models and the Nokia 6120, I just have not got around to them yet.
You can find the specs by searching for "ETSI CGDCONT", the 3gpp.org website is very informative.
Basically I set up 4 contexts, but usually you only need to use the "tesltra.internet" APN