I have a Samsung A717 that works perfectly. Little smaller than the Sync with more features. Goes for pretty cheap with a contract right now. I get about 50KB/sec at the low end (EDGE is about 10KB/sec) which goes to around 150KB/sec depending on signal strength. Quite reasonable for browsing and works perfectly with Rhapsody. Unfortunately, there's a blackout area right on my way home from work so I can't really listen to Rhapsody in the car there. Signal strength is pretty good for most of the city (St. Petersburg, FL) even indoors in most places. I really like the phone as it's very small and perfect for voice/data usage and my N800 can do everything else.

The RAZR v3xx has the advantage of having a 3.6Mbps modem (versus the 1.8Mbps modem in every other model in their lineup right now). That said, AT&T hasn't actually turned on the 3.6Mbps speeds and it probably wont happen before the end of the year.

The MediaMAX Unlimited plan will work fine for tethering as long as you change the "isp" in the login info to "wap". Just try to keep your bandwidth usage down and don't tell any reps. :P