Here are links to some applications I have found worthwhile on my E61 (S60 v3).
Google Maps -- Go to m.google.com on your phone and download Google Maps. It should autodetect the phone. The turn-by-turn navigation is a bit lacking, but the application is free, and you get map, satellite AND street view, plus search! Also, it supports Latitude, so you can have it run in the background and let select people find you on a map. As a bonus, on my E61 which only has cell-based location, it can use an external Bluetooth GPS receiver if one is available. Cool!
Google Mail -- Go to m.google.com on your phone and download Google Mail. It should autodetect the phone. For me, at least with encryption enabled, the current version is really slow, but it's a good interface to your gmail, assuming you use gmail. It can run as a background task and buzz when you get new mail.
Google Search -- By now you should have gotten the gist. What this does on my E61 is retask the ctrl key to launch a search term input. So to launch a Google search, I just hit ctrl, type in the string, hit enter, and it automatically invokes the browser, goes to Google, and presents the results.
YouTube -- Go to http://www.youtube.com (NOT m.youtube.com!) and find the client download that's cleverly hidden there somewhere, or download from this link from Symbian Guru.
Mail for Exchange, available from Nokia. It integrates with my work Exchange account and gives me access to the corporate directory. More importantly, it syncs my address book, calendar, and tasks as well, if desired. It seems to work very well.
Y-Browser -- Like File Explorer for your phone, and free. You may have to figure out how to let your phone install unsigned applications, or use a signing gateway to sign the package.
Handy Taskman -- like hitting ctrl+alt+del on your phone. Shows you memory, tasks, lets you kill them and switch between them. A lot better than the built in task manager, but $20.
Calcium -- A basic calculator, but with a excellent interface, especially for phones with just a number pad! Also, free.
I also use a product called RemindMe which I bought, but it hasn't been developed for three years now. Basically, applications can override the normal alarm behavior of the phone, letting you set different ring tones to email, MMS, SMS, missed calls etc. and allow the phone to bug you every so many minutes until you acknowledge it. This is so I can replace my pager and won't miss pages even if I don't hear the initial message noise. There appear to be other applications, like mRemind, for the same purpose, but I haven't tried them.