I went from a BlackBerry Storm to an HTC Droid Incredible on Wednesday afternoon and I've already found, installed, and configured the following, so this is really easy stuff!
Advanced Task Killer - Allows you to manage which applications are open / closed instead of letting the Android OS do it for you. Beware; some say these types of applications can hurt your phone rather than help it, not to mention that it's a total non-essential as the Android OS already manages your open/closed applications for you 100%.
AndroNews - A consolidation of various news sources (CNN, etc.) Basically a gigantic newspaper.
ASTRO File Manager - What I use to install APKs, and generally a great way to browse the contents of your phone and SD card.
Backgrounds - An application of thousands of wallpapers to download and implement.
Bank Of America - Online banking application.
Countdown Widget - I use this to keep track of how long it will be until a specific date / event / holiday. Currently, tracking when NFL 2010 kick-off will be, and when the Faith No More shows in Brooklyn and Philly are.
Countdown To Christmas Widget - I love Christmas!
Countdown To Halloween Widget - I love Halloween!
Facebook Sync - Automatically populates the default images of people's profiles into their corresponding phonebook (or "People") entry.
Foursquare - Becoming more and more well-known; you "check in" to public places you're at, connect with your friends, arrange meet-ups, earn "badges," become a "mayor" of places you frequent more than others, post updates through Facebook/Twitter, etc. Just don't abuse it or you'll annoy everybody.
MLB At Bat '10 - Crucial for baseball fans.
NESoid - Nintendo emulator. Loads ROMs from your SD card.
NFL Mobile - Crucial for football fans.
Opera Mini 5 beta - An alternate web browser to use other than the native one.
Remote Desktop - RDP for your cellular device.
Speed Test - For testing your upload/download speed from wherever you are.
Twidroid PRO - My preferred Twitter application.
Uninstaller - An alternate method for uninstalling software from your phone.
WeatherBug Elite - An alternate weather application.
Where's My Droid - Allows you to remotely disable silent mode on your phone if you've lost it and you're calling it from another phone to locate it. Also has GPS location abilities.
Wikidroid - A Wikipedia application.