iPhones get a much bigger subsidy from the carriers. This can be deduced from the ASP that Apple, HTC, RIM etc report. iPhone ASP has always been $600+, while HTC, RIM have ASPs around $300-400 (Samsung smartphone ASP is even lower). This can also be seen by looking at contract prices outside the US. For example, in the UK all phones can be had free on contract, but the monthly amount you pay for an iPhone is much larger than for a top of the line Android (see the O2 or Vodafone UK sites).
The reason this is not reflected in the contract-less prices is because US carriers have a very strong incentive to inflate them to force you to choose contracts.
Actually, in your link above, iPhone 4 prices start from $859. $719 is the price of the 3GS.
I don't know how it is in Australia, but the contract price discrepancy between Android phones and iPhones is well known in England. For example, O2 sells the Galaxy S2 for free with a 24 month £42 plan, while the 16GB iPhone 4 is free on a 24 month £67 plan.
The Galaxy S2 plan gives you a bit more data, and you do have more flexibility with Galaxy S2 plans - you can choose to pay more for the phone and less for the plan for example. (Of course, you also have a big choice of cheaper Android phones too).
The reason this is not reflected in the contract-less prices is because US carriers have a very strong incentive to inflate them to force you to choose contracts.