My must haves:
1. Tasker: Automate everything on your phone. Seriously. Pretty high learning curve, but the website has a lot of pre-made scripts you can load in. This app is the balls.
2. Google Apps: My must-have google apps: Google Docs, Google Goggles, Gmail, Google Sky Map, Google Maps, Google+, Youtube
3. Touchdown by Nitrodesk: For exchange e-mail. I love having tasks integrated.
4. Adobe Flash Player: Pretty self-explanatory
5. Dice Bag: Best dice rolling app I've found. Use it for my weekly D&D game
6. Fantasy Football Monster '11: It's worth the money. Way better than the yahoo-developed fantasy football app.
7. Barcode Scanner: For barcodes and QR codes
8: Keyring: Keep all your key chain rewards cards on your phone and backed up online.
9. Last.fm: My personal favorite music streamer. I love the concept of Pandora, but Last.fm just has a wider selection.
10. Linkedin/Facebook/Twitter: Only installed for syncing purposes
11. Tweetdeck: Best twitter/facebook combo app. Hopefully they add G+ support soon.
12. Netflix: Self-explanatory
13. Note Everything Pro: Best note taking app
14. Slingplayer: If you have a Slingbox, you know how awesome this is.
15. Swype: Still the best keyboard, in my opinion, and I've used them all.
16. Tapatalk: Great for browsing forums, which you probably do if you're reading this
17. Trillian: By far the best instant messaging app. I have tried all of these as well.
18. ScoreMobile: By far the best sports ticker.
There are some other apps that I currently use, but I'm hoping I will be able to do away with once we get ICS because of the base UI improvements. These include LauncherPro Plus, Pure Calendar Widget, and a few others.