A couple I haven't seen mentioned that I like are
iFlix - if you have NetFlix, you need this app. View and re-arrange your queue on your phone. Plus it looks great.
MobileCast - download and play podcasts directly on the phone without going via iTunes. Not much use if you plan to sync regularly, but great if you are not for some reason (stuck in an airport, whatever). The latest version adds video podcasts (though it's not yet on installer).
NetServices - like Services.app, but with more toggle switches, so you can toggle stuff like FireFly (iTunes streaming), Apache/lighthttpd web server, SSH, AFP, Auto-lock, etc, etc. It only displays what you have installed. Plus it shows your IP address, so no need to dig down through Settings in order to check it when you connect with SSH.
AFP with Bonjour - I've just got this so haven't played with it much, but you can now connect to the phone with AFP. So with Bonjour on as well, your phone just automagically shows up (in leopard at least) in the list of servers so you can transfer files without resorting to SSH.
gPSPhone - play GBA games. Still not 100% but getting there.