I've been using mobile applications for a while and I've been developing them as well. Over time, I came to some conclusions about what makes an application better compared to other applications. Or at least, that's how I see an application that is of a really good quality. Although these items might seem pretty obvious, these are often neglected in a surprising number of applications.
1. Stable and reliable
Before releasing an application, it should be well tested under multiple conditions. Disable WiFi, disable the cellular data connection, set the phone to airplane mode - test the app in the most extreme conditions, because if you won't do that, your users will. And there is nothing less "cool" than an application that crashes and you have no idea what caused it because there was not enough testing.
Make sure the application doesn't over-use system resources. If the platform offers background application support, make sure that your application doesn't consume too much memory and CPU power - otherwise chances are the next day the application will no longer be present on the device.
2. Consistent with the platform
Every mobile platform out there has its guidelines when it comes to applications that look consistent with the work environment. This applies to UI and overall user experience. If it is Windows Phone 7, then you would probably want to use Metro-like components, including buttons, text boxes, pivot and panorama controls and every other consistent control. If you are building an iPhone app, you might want to use the standard application bar and the standard navigation controls. Going outside the boundaries when it comes to consistency causes a lot of discomfort for users who have well-formed mobile platform usage habits - every user has certain expectations when it comes to using a system, and that applies to subordinate applications. That's what guidelines are for in the first place.
3. Loads fast
I honestly will not wait for an app to load if it takes more than 5-7 seconds (although even this is quite significant). Of course there are applications that might need unusually large amounts of data at startup and if that's the case, you should let the user in to the main app screen and perform the loading operations in a separate thread, so the user knows that something is going on. A good example here would be Facebook and Twitter applications for WP7, iPhone and Android - the application is loading the main UI and shows some actions related to the service. At the same time, the application processes web requests to retrieve notifications, messages, replies etc. (depending on the service). Do not start resource-consuming processes at the application startup and leave the user at the splash screen (even if there is a Loading... label) - after a couple of seconds of waiting, the app will be closed.
4. No UI hangups
Under no circumstances should the UI thread be blocked. The instant reaction to this is - "The application froze. Have to close it." Most users will follow this "instinct" without even knowing that maybe there are some legitimate data manipulations performed. All mobile platforms offer thread separation and if there is a job that requires some time to complete, have it running as a secondary thread to avoid user frustration.
5. No Ads
This is more of a personal opinion rather than a recommendation, but I don't really like to see ads in mobile applications. Maybe in some cases those are effective, but personally I never click on ads and sure hope that there is a version of the app that is ad-free. There are other ways to get income from your applications, and if you plan to do so, make it a paid app but ad free, rather than free and filled with banners.
6. Considers the user as a valuable consumer
By this I mean that the developer considers that sometimes the user doesn't want to over-pay for the services provided by the cellular network. If there are large amounts of data to be downloaded, it is very thoughtful to inform the user that "hey, we know that you want to get this, but it is going to cost you a bit more if you do this via 3G and not WiFi"
7. Provides worthy functionality
How many flashlight apps are there in the application marketplace on any platform? How many news aggregators? Lots and lots. What are the chances to get some time in the spotlight with an app like that? Besides, why would you want to work on something that is already there without adding additional functionality that will make your application unique? Also, consider that your users are smart and you don't want to provide a $50 application shell for a web service that can easily be accessed through the web browser on the same mobile device. This example applies to WolframAlpha - when the iPhone application was first released, it was priced just like I mentioned, but you still could use their web calculation app for free (plus, there is a mobile version of that site). So what's the deal?
Overall, I am not trying to say that for an app to be successful you have to follow the ideas outlined here. Not at all. These are more like personal thoughts on what would be a great app in my own vision. Feel free to let me know if you have any other criteria that are important to you in mobile applications.