Jessica, I'm gonna be honest: Windows Mobile has a LOT of flaws, but at this point I think the flaws in Palm's ANCIENT OS are probably worse, overall. But I still am sticking with the Palm Treo for one reason, that I'm guessing might apply to you as well: without easy access to a Windows machine, installing software on a Windows Mobile PDA is an enormous pain in the keister.
You see, the vast majority of Windows Mobile software is distributed inside Windows-only EXE install files. This despite the fact that there is a perfectly servicable (if a bit primitive) method for installing Windows mobile files that is cross-platform. Some providers will provide access to these CAB files with a bit of digging, and others will send them to you if you request it in an email, but it's a pain, and the install process is not exactly simple.
Of course, for software that you only really have to install once, that's fine. But I never got Vindigo to work, despite tons of tinkering with Missing Sync, and it's not formall supported. Zagat guides would need to be updated yearly, with all of the obnoxious emailing for the updated CAB that entails. And I simply couldn't easily tinker with my programs the way I like. Thus, I sold my Windows Mobile PDA and bought a Treo 650.
If you have a Windows PC available that you can use for installation (and if you want, syncing Vindigo) then Missing Sync does a perfectly good job syncing the actual address book/contact stuff. If that's easy for you, I'd recommend going for a Windows Mobile phone (though make sure to play with it and read up on it before buying). It will also let you shop for Windows Mobile software that IS supported by Macs. But if it's going to be a constant frustration, like it was for me, then you'll want to stick with palm.