I REALLY like "The Weather". It was a rocky launch, but it has really matured and is great.
Frustrated by what was available, I created a weather app for Android which did what I want from a weather app: smart alerts about tomorrow's weather. In talking with people about it, I learned there are many different ideas about how the perfect weather app would behave for different people. This is not surprising; weather information is only useful in the context of how it would change your behavior. Since everyone has a different schedule, a consistent and simple interface is not likely to be possible.
The name of the app I created is "Anticipates (Weather)". comments are welcome!
https://market.android.com/search?q=Anticipates&so=1&...
Same results on a real phone.