If your phone is jailbroken, here are a few apps I like:
backgrounder - allows for apps to run in the background
winterboard - change wallpaper behind icons, themes, etc.
pdanet - tether your phone wirelessly to your laptop (allows laptop to use edge/3g signal)
cycorder - record video on your camera
bossprefs - hide unused apple app icons
flashlight - much brighter screen than apple will allow, also a strobe light
AOL Radio: Like XM, but is made up of local stations (I think) from all over the country. For example if you are from Houston and are traveling you can still listen to 610. Plus it has a lot of really specialized stations such as band specific stations (Dave Matthews, Green Day, Korn, Pearl Jam, Smashing Pumpkins, Radio Head, and many more)
Mobile News: I use this for my news updates. Like AOL you can set a local destination and get local news wherever you are without having to go to their websites.
Whitepages: Simple program to look up phone-numbers and address. Also features a reverse number look-up which can be helpful, but if its a cell-phone you don't really get too much info (other than what network the phone is on)
Air Sharing: Lets you upload files to your iphone. I don't use this at all, but for someone else I could see this being really helpful. You can also view the files you upload, such as PDFs.
Stanza: A book reader. It has a lot of titles available, but mostly classics. I grabbed a bunch and read them when I don't want to listen to music, surf the web, play games, or watch a movie.
Ocarina: turns you iphone in to the flute thing from Zelda. I just picked it up today when it was on sale, and haven't really done too much with it.
As for games I have Tris which you can't get any more, Sudoku, TouchMIne (mine sweeper), Tap Tap (supposed to be like guitar hero, but I don't like it), something called Same Game which is a block puzzle type game.
My favorite is Aqua Forest. It's not really too much of a game, but it really uses the iphone well and it's what I show off to people when explaining how cool the iphone is. Basically you have some puzzles that you have to solve. They usually involve water and you redirect the flow of water by tilting you iphone. The water looks incredible.