Remote is an app made by Apple which allows you to control the iTunes on your computer via your home Wi-Fi network. You can also set it up so friends can make "requests" with their iPhones. Pretty neat for parties.
Convert is the best conversion app I have found so far. It does Angle, Area, Data (Kilobytes->Megabytes and etc.), Density, Energy, Length, Mass, Power, Pressure, Speed, Temperature, Torque, Typography (Points->Picas etc.), Volume and Currency with almost ridiculous amounts of units for each category. Nice interface, too.
Urbanspoon is super neat. You may have already heard of it as it was featured in the iPhone ads a little while back. Urbanspoon finds restaurants in your city. It has a slot machine-like interface which allows you to "hold" categories of Price Level, Location and Food style (Italian, Kosher, Fast Food etc.). You then shake your phone and the little slots whirr around and then it finds you a restaurant. You can also view restaurant locations with Google maps, and read reviews on the web. Urbanspoon also has a kind of cool social networking component which means you can share recommendations and read and write reviews for places you've been.
AroundMe is very much like a much-expanded version of UrbanSpoon in that you can view not just restaurants but also Apple Stores, Banks/ATMs, Bars, Coffee Shops, Gas Stations, Hospitals, Hotels, Movie Theaters, Parking, Pharmacies, Supermarkets, Taxis and Theaters. It has full utilisation of Google Maps so you can see locations as pins and get directions within the app, save locations, email coordinates, view contact details for businesses and even post to Twitter or Facebook.
BubbleWrap is another one of those incredibly simple yet crazily addictive apps. It's exactly what it sounds like. Poke at your iPhone to pop bubble wrap, do it as fast as possible, set high scores.
Rope'n Fly is basically Spiderman for the iPhone. You've got a dude who shoots ropes to swing between buildings. Your objective is to keep him off the ground for as long as possible. This app is paid but there is a "lite" version for free.
I Am T-Pain: AutoTune. on your iPhone. Surprisingly high quality, it's actually a strip backed version of the Antares plugin which is probably in the top two for professional autotune plugins. Download tunes and sing along, save recordings, choose the key you tune to. This is a paid app.
Tap Tap Revenge: Guitar Hero or Dance Dance Revolution for your iPhone. Little notes fly down your screen and you tap the phone in time. Plenty of free tracks to download, surprisingly good artist selection. There's a few verisons of this. TTR 2 is free, the others are a dollar or so.