The new launched Google Moderator has this question as one of the featured votes. And here are some top ones in each category at this moment:
Games:
Tetris… you can’t go wrong with Tetris.
Be sure that FLASH PLAYER games stored locally could be played… The lists of games available on the web is amazing, and any developer can make is own game quickly.
Lifestyle:
Travel logger for all kinds of trips: bike rides, hikes, etc. Logging events (configurable) on the phone such has time, GPS coordinates, compass orientation, time, currently playing song, photos, local temperature, etc. Syncs to Google Spreadsheets.
Share your position with friends on your gTalk/IM list. e.g. if you want to meet someone, you can check where he is or pinpoint the location when you don’t see each other. Or, an alert when some buddy is approaching/nearby you.
Multimedia:
Podcasting app that lets you subscribe to podcasts, and automatically keeps a few downloaded for you to listen to.
I’d like to see a VLC portable application to see tv streaming from my internet provider!
Productivity:
An application to synchronize local contacts with Google contacts?
Would anyone like to see an android to do list?
Shopping:
Wishlist App. Scan any barcode, and that item is placed on a wishlist that you can view and share with family and friends. Adding a note to each item would be allow friends to understand the item. ex:”Rachel would love this for her birthday!”
Best prices: You are in front of an amazing sales, but you are not aware of the real price of the product… Type the product name and find the lowers prices on the web. (not sure an app is needed a lot of websites do that). More like a widget.
Tools:
PDF Reader
SSH client to remotely administer servers
I think some of them already exist. For example for SSH client you may try Connectbot. Compare Everywhere is all about instant checking to find best price. For the applications that are not available yet, it is the perfect time for mobile developers to jump in and code them. Personally the first one I wish I could have (or write) is a podcatcher application. Currently I am using Canola 2 on my N810 daily to download and listen podcast program. For me it is the top one I wish to have.
I am not sure when Android handsets will have Flash support. The T-Mobile G1 does not support Flash, but later Android models will according to Bill Perry from Adobe. To be able to download and store a Flash game locally is a good feature. For desktop computers, now you can drag and drop an Java Applet to desktop with new Java SE update 10. For iPhone and possibly Android you can create a desktop shortcut for a webpage. Be able to do it for Flash files is an intuitive thinking.
Maybe it is the time to get a T-Mobile G1 before it is sold out again 