OTA sync is more a question of "how" rather than "does it exist." There are a number of low cost mail providers that support MS Exchange, and that provides OTA syncing. On WM platforms, there are also apps around to sync to GMail OTA (probably for the iPhone as well, but I don't know for certain). If you ask around for opinions on the in the Lounge, I'm sure you'll be pointed in the right direction for what you want.

If you like WM and are looking at AT&T, I can highly recommend the Fuze (particularly with the updated ROM they released). Good performance, lots of RAM, microSD expansion, GPS, Voice Command, A2DP support. Very solid phone that I expect to have a good long time.

If you don't mind spending a bit more, getting an unlocked Touch Pro 2 might be interesting as well. It may not support US Data networks, though, so check the specs carefully. Rumor has it AT&T will be selling the phone, but be warned that HTC & AT&T can combine for some wonky first passes at phones that get fixed with later ROMs. AT&T wants their stuff on the phone, and that seems to leave some things that should work better a bit broken.

Good luck!