Here's a list of all of the software I have added to my phone, all of which (so far) is free or in trial mode. Each one adds quite a bit to the phone's capabilities. Not only is there lots of free software out there if you can only find it (I spent days finding all this stuff), but there's a growing list of Open Source software as well. A lot of it is being written in python, which is SO much easier to program for S60.

And don't forget to upgrade your firmware to get new capabilities and a faster phone! (See bottom) No matter how recently you bought it, it probably doesn't have the latest software update yet.

[Update: see the comments, and also I forgot: Nokia's accelerometer kit and the cool software that uses it, truphone for totally integrated VoIP over WiFi, a great minimalist theme, and the Python kit. I'll post more about them later.]

Free Software (open source)

• Frozen Bubble - a popular puzzle game ported from Linux. Nifty. How fast can you get to level 100? (You can save games...)
• LogExport - I haven't used it yet, but it gives you a spreadsheet for your phone usage (call logs etc.) and that sounds useful.
• MobileGTD - "Getting Things Done" app basically helps you manage your todo lists, projects, and so on. Written in python, I think this is the future of a lot of open source S60 development.
• MidpSSH - a nice Free SSH client. Unfortunately, because it's Java, it's impossible to use it as a SCP client. In fact there doesn't seem to be an SCP client for S60/N95, bummer. (I use WebDAV over HTTPS to access my files securely, but it's read-only.)

Free software from large companies

• Opera Mini - a fantastic browser, although you don't really need it on the N95 because it has a good browser built in. Opera Mini probably reduces your data usage substantially though. On the downside, there's no HTTPS (secure connections) because the opera mini server unpacks the data and streamlines it before sending it to you.
• Google Maps - this is a great app, because it has satellite photos built in and also it can give you a rough position when you are inside using cell tower IDs. It also has location based search, but the location based search on the built in GPS software seems to be just as good or better.

Freeware

• Calcium - a really nifty calculator with an innovative interface. Definitely a must-have.
• SExplorer - a file system browser that gives you access to the WHOLE file system, not just the limited bits that the built-in explorer can show.
• Nokia Sports Tracker - a very useful program from Nokia Labs, it uses the GPS to track your sports activities such as walking, hiking, jogging, etc. You can view graphs of your speed vs. time, and other things, and export the route you took to Google Earth.
• S-Tris 2 - a Tetris clone, very well done and faithful to the original. Which is all I want in a tetris app. No crazy "3D tetris" please.

Commercial software with free trials

• Opera Mobile - I'm going to try this out in case it's better than the built-in browser. The built-in browser is very capable, impressively so, but. It has a few annoying "features". 1) No way to save passwords for HTTP authenticated sites. 2) Doesn't remember my zoom level (I like 75%). 3) No way to delete some annoying folders in the bookmarks manager. 1 month free trial.
• Salling Clicker - total remote control over your Mac or PC. Slick interface. Works over Bluetooth, WiFi, whatever. Run presentations, control iTunes, and many other apps. Very cool. Paid version adds more features.
• Lament Island (click "try") - wow, this is a cool game, quite sophisticated level of 3D graphics (maybe like original Tomb Raider) and an extensive story-line. By Chinese company Simlife. Here's a YouTube video preview.

Free firmware updates

• Nokia Software Update has just released the v15 firmware for my 8GB and it adds some cool stuff, notably more speed, a video editor, and support for Flash Video (e.g. YouTube). Nice. You can only update from a PC, which is super annoying. Also, be sure to backup before you update though. Why, Nokia, can't you make this process easier???