My favorite apps so far are:

Pandora - Fantastic free music application.

Shazam - Works flawlessly, every time. Then when you have a song, you can hit one button to buy it from iTunes, or another to play a related video from Youtube.

Texas Holdem - GREAT game. Fantastic production values. The best poker game on any platform, based solely on playability.

MLB At Bat. Get live results and video clips (new ones uploaded as they happen, and great performance even on Edge.)

Twitteriffic/Twinkle - Front ends for Twitter. They work great.

Jott - Works almost like magic. Your recording is sent to a team in India that transcribes it. Seriously.

ToDo - By http://www.appigo.com. Todo list that interfaces with a web component. Built your list online with a real keyboard, then sync it with your iPhone. Or add items on your iPhone and sync it back. Works with Toodledo, which made it an auto-buy for me.