I don't think any of my apps are MUST HAVES, but I certainly have my favorites.
Pandora is a must have for me when I forget to charge my iPod- I listen to music on the way to and from school, and walking around campus.
Beautiful Widgets isn't a must have, but any sort of weather widget is. That's just the one I prefer. I use it a lot in the mornings to figure out how to dress for the day.
Gentle Alarm, or any type of alarm, is a must have. I know android phones come with stock and those work for some people. The stock alarm works for me in some situations (I love the stopwatch and timer built in to the stock one, comes in handy). But I love the fact that Gentle Alarm is one of the apps that has a fade in alarm. It never startles me in the morning, and I feel like I wake up more refreshed because of it.
Quick App Clean Cache is a definite must for me. It works for both rooted and unrooted phones, but with a rooted phone you can clean all apps with one click. Otherwise, it lists all of the apps with cache and you can clear them one by one.
Launcher Pro Plus is a must have for me personally. Mainly because I love the Widgets that come with Launcher Pro when you pay the $3 donation and because I don't like the stock one all that much.
Root Explorer and
ROM Manager are must haves if you're rooted. Root Explorer allows you to remove/rename files and ROM Manager is for, of course, ROMs.
ClockworkMod Recovery and
Titanium Backup are must haves if you want to back up your apps (Titanium)/data and your current ROM in case something goes wrong (Clockwork).
Google Navigation is a must for obvious reasons.
That's really it. Anything else I have is to make my life easier/is just for fun.