Telstra has a special 3G "Bush Phone" with greater range than other 3G phones, thats just been released which has a small extendable aerial. A mate was given one last week after he complained of no mobile coverage in the center of Port Phillip. This thing was allegedly tested at Mt. Hotham and demonstrated a 200 km range.
It's larger and less flashy than some phones, but it sounds like what you might want.