You absolutely have to get Google Maps Mobile and Windows Live Mobile. I might have the names wrong but they are basically mobile versions of google maps. Both are extremely handy and free. The only thing they are missing is actually knowing where you are but if you have a bluetooth GPS unit they can do that as well.

I'm especially fond of the Google program. You can basically see the full map that is online with the same levels of zoom. It is really helpful. Windows live is really good at finding businesses and nearby locations. Both work great with EVDO. Just search them with google through your phone and you should be able to get to the download links.

Pretty much everything else I do with the phone is through Google as well. There is an app for Gmail but I just access that through pocket IE. Adding EVDO really does open up a lot of possibilities.