Flurry - (http://www.flurry.com) Mail and news on my phone.
Also useful are:
Google Local (http://www.google.com/gmm) Maps on my phone.
Opera Mini (http://www.opera.com/products/mobile/) Web browsing on my phone.
EQO (http://www.eqo.com/) VoIP and IM on my phone.
Note that these all work with data services from Cingular and Sprint, but T-Mobile has recently started preventing the use of these services on their phones unless you buy an "unlimited" plan. Verizon either charges a few dollars a month for them or doesn't have them available in the first place.
If you have Boost mobile service, you should also check out Loopt (http://loopt.com) - a service that lets you tell your friends where you are.