Since i reload my phone every month this is a pretty easy list for me. In order off my new app list, these are all a must when i get a new device.
Amazon App store: Free app every day makes this worth installing and keeping on the phone. (Its required to run the
apps you download.) Most free
apps are crap, but there have been some good ones here and there.
Battery Calibrator: Free from the market. Resets battery stats without rebooting. (Not all ROMs have a reset built in, Just my recovery)
Facebook and Twitter for android: For obvious reasons.
Office suite pro: Free download one day from amazon. I use it now and then to edit word documents.
Printer share: Another free amazon app. Allows me to print to any IP printer without issue.
Quadrant: Market, free, I use this to test a new phone when i get it. Also works good on gauging new kernels.
Realcalc: Market/Free A calculator with more scientific functions. The basic sometimes wont cut it. Free and it gets the job done.
Sound hound infinity: Seems to work better then Shaazam on most things. I have Shaazam encore as well. Both were free from amazon at some point.
Yahoo sports: Market, free, Use this to track NFL teams on Sundays.
Titanium Backup: Market, Free/paid NEEDS ROOT. Works well for backing up free
apps that disappear from amazon. Not the all in one backup solution it claims to be since it can cause major slowdown when switching OS versions and restoring app data. Works well for app alone.
Opera Mini: Market, Free, Super fast because it caches web pages on opera servers for faster delivery. Use it for heavy browsing sessions and for a backup.
Smart keyboard pro: Free/paid, Market. Best keyboard i have found for my needs.
Google Music Beta:
ICS should come with this. But if it didnt, i would download it day 1. Free cloud music and lte? Done and done.
Must have game pack: I install the following games at some point just for waiting rooms and such.
Peggle, Angry birds, cut the rope.