I'm not sure if they go that far south, but Prairie Mobile Communications has (or had) a fixed-wireless service through parts of southern Manitoba.
Working with a fixed-wireless provider in NW Ontario, I can also confirm that "you get what you pay for". A free-standing pole with guy wires anchoring it is cheaper in equipment/capital cost but requires more (and more skilled, and more expensive) labour to install. Also not legal in some places.
There are many people in southern MB who can erect towers & poles (cheaper than WiBand), the challenge is finding them... And then convincing WiBand to just use the existing tower.
For halfway-decent or halfway-reliable service, expect to pay about $3k in install costs w/o a contract. On a contract, that often drops to $1k, $100-$300 or even $0 depending on contract length and provider.
Barret's Xplorenet is a good option if a) no-one else can reach you, or b) installation of a tower or mast is contra-indicated for some reason (land unsuitable, prohibited by wife on aesthetic grounds, etc.). Otherwise, NWO has mostly the same experience with them - it's better than dial-up, but worse than everything else.
-Adam