One thing that I hear from a lot of people with iPhones is "I wish that it had (insert program here)."
While I agree that the iPhone needs third party applications, or at least widgets, the void is being filled by an increasing amount of slick Web applications that run on iPhone's Safari browser. The problem is that it's difficult to keep up with them all.
A number of iPhone application list Web sites have popped up including iPhoneWidgetList.com (about 160) and iPhoneApplicationList.com (~120) but by far my favorite is iPhoneAppr.com because of it's slick iPhone interface.
Leaflets are optimized versions of popular sites (like Wikipedia, Flickr, Upcoming, Del.icio.us and NY Times, for example) that run extra fast on iPhone - even on AT&T's pokey EDGE network.
Bookmark these in Safari and they'll appear on your iPhone after your next sync.