Windows Mobile
I have been using an Audiovox SMT5600 Windows Smartphone for about a year and it is awesome. It never crashes and the call quality is fantastic. Plus, i can sync my movies, personal videos, pictures, and music with the phone and it plays them all with fantastic quality. Even Palm has started using Windows Mobile 5 in the new Treo. It really is a fantastic platform, so give it a try and i think you will be impressed.
Also, unlike the iTunes phone, Windows Mobile is an open platform and not limited to a single vendor (iTunes) for online music. While iTunes, iPod, etc are excellent devices, they are a closed platform controled by Apple.