That's because they can control the iPhone but not Android. They want you to pay for tethering specifically regardless of your phone and their contract T&C's forbid it if you don't pay the extra, they just can't pro-actively stop you on anything but the iPhone
Once you get to the likes of the 6700, if you still want cheaper you'll sacrifice performance and flexibility. The radio hardware simply wont be able to deliver a great service, even the 6700, as good a phone as it is, is old-tech when it comes to data performance.
If tethering is your one and only priority, I would look for a second-hand MiFi and then buy a cheap mobile to compliment it. The overall result will be far superior.