My ISP recommends getting a 3G modem with an external antenna.
Then they should have no problem with letting you try it out first for say a week or two, I know a few people on Telstra 3g in country Victoria that still have problems even after getting an antenna, My best advice is talk to your new neighbours, See what they use, Go into a PC shop in the new town and ask them what works, You can also try a pre paid option, Most Woolies and Coles have them, The modem costs about $50 and you get 1 GiB of data with that. Above all do not let them talk you into a contract without a written guarantee that you will have good signal, You dont want to be stuck with a 2 year contract and no internet.
Maybe your phone can be used as a hot spot?
I agree, Try tethering your PC to your mobile and see how it works.