Here's my list of must-haves. My understanding of must-have apps is I will get them in my devices no matter what after every new flash of ROM, either reinstalling from play store or restoring via backups. May not be for everybody but for those who are not already using these apps, you might want to check them out. Note that some of these apps require root - labelled with a "(R)".
Utmost apps I will install as a habit routine
Titanium Backup(R) - Both my devices have this running scheduled backups. A must for all flashamaniacs like me.
Root Explorer(R) - my personal favourite root file manager
The rest..
AdAway(R) - cure for annoying ads in browser or apps. I also recommend AdBlock Plus for Android.
AirDroid - wireless file manager/client. I can't find my USB cable sometimes ;p
Cerberus(R) - security app. I hate to lose my phone.
Lux Auto-Brightness - wonderful app to control/replace auto-brightness in Android
Mx Player - best player for video, even streaming
Poweramp - like it or hate it. It works well with the sound mod I'm using below.
SD Maid(R) - cleans and clears trash. Much like CCCleaner for PCs.
Viper4Android(R) - if you are a soundphile, check out this awesome mod on XDA forums
here.