Microsoft released their Bing iPhone app and It looks and feels really nice and I love all the fancy animations built in. The main features are:

• Image Search
• Movie Search
• Maps lookup
• Search for Business Locations
• News Search
• Route Search
• Search by Voice Record

And It's totally free =)