Let's see. Android phones with unrestricted Tethering and Wi-Fi hotspot are Nexus One, Nexus S and presumably Galaxy Nexus.

Tethering on any Droid phones are encumbered by Verizon. You have to pay the tethering plan to have this feature enabled. The same goes AT&T Android phones with "crippled" tethering capabilities.

iPhone supported carrier-sanctioned tethering pre-iOS 4 (iOS 3.x in 2010), just not in the US with AT&T. Different carriers handle it differently.