I do freelance IT work these days. My blackberry is my business lifeline.

Back to the original question (with OTA links) for the ones I use daily. (I find some links work best if I don't have the built-in browser set to IE emulation.)

The free ones:

beyond 411 - fabulous (and fast) localized yellow pages. Set up Home, Work, and Other locations. Remembers all the Other locations you've used. If you look up an address, you can quickly set it to the Other slot.
http://thebogles.com/blog/projects/berry411/

google maps - with traffic and GPS (or cell tower) auto-locating
www.google.com/gmm/

opera mini - does some things better than the built in browser, some worse. I routinely have both open.
www.operamini.com/download

The ones worth their small fees (trial versions available):

message alerts - customized alerts, by sender, time of day, etc. My clients can use a code to page with a true emergency at night. Anything else won't set it off. (I'm not sure how well supported it is since Apptix purchased it, though. It took me a week to get a new code when I replaced my blackberry.)
http://www.webmessenger.com/products/mablackberry.htm

pocketday - puts a summary of all your main info (new messages, missed calls, calendar, tasks, etc.) and a bit extra (weather, stocks, rss feeds) on the front screen. Very customizable.
http://www.crossriversystems.com/pocketday_downloads.htm

empower mail viewer - html mail viewer. My blackberry only does text email.
http://www.mobihand.com/eidevices/download.asp?id=16058&pdid=518595

If I still worked for the company I was with, I'd have the remote connectivity tools, too.

Good discussion site here: http://www.blackberryforums.com/

-jk