The first thing I think mac users should do is setup an Admin account and then log into that account and remove admin status from their 'main' account. This is good from a security standpoint and recommended by apple. After that, this is my list of must have software.
VLC - free video player
Handbreak - free dvd to mpeg converter
TextMate - not free, but AWESOME text editor for programing
CyberDuck - free semi decent ftp client
Adium - best chat program ever
AppCleaner - free, my favorite program for uninstalling apps, widgits, and more
Transmission - free, everybody needs bittorrent at some point.
BusySync - not free, allows google calendar and iCal syncing. I am also looking at some other software that does the same thing.
TrueCrypt - free, I need encrypted containers for my private data
Growl - free, this will probably get autoinstalled by something above, but it is a useful notification system. I also use growltunes which comes with growl.
Firefox3 - free, I use this mostly for testing. I prefer safari.
Xcode - not only because I am a programer and want to write mac apps, but because it installs all the build tools you could ever need for doing most any kind of programing.
iWork - not free, but cheap and a very good application suite for most everyday office tasks. If you need full MS compatibility, I suggest MS Office 2008. I can not suggest Open office until Open office 3 is released.
SimplyBurns - Sure you can use Disk Utility to burn ISO's and you can use burn folders to burn files. but simply burns is just so easy to use. I high recommend this app.
Unarchiver - great little tool for decompressing formats apple does not support.
iStat Pro - great dashboard widget that will show you everything you ever wanted to know about your hardware (ram usage, hard drive info, battery health, temps, cpu usage, etc)
Software I've tried but did not like:
Coda - seemed great, turned out to not be as powerful as I am used too. This is a all in one web programing editor.
FileZilla - I love it on windows and linux, not so great on a mac, very buggy. FTP client
That is a good chunk of what I am using now. I also have a few suggestions for your setup.
1) Flatten your dock. This is a personal thing. I can't stand the 3d dock. I just can't tell what apps are running. I like it flattened. Do do that (on a per user basis) just open the terminal and type in
defaults write com.apple.dock no-glass -boolean YES
killall Dock
a) To put it back to 3d replace the Yes with NO and run the 2 commands again.
2) As I said before, make an admin account and remove admin status off of your account before you do anything. You will never need to login to this account again. OSX will prompt you for the Username and password for this admin account to do any actions that require 'root' privileges. This will help protect you from the world and yourself.
3) First, when you open safari, go into preferences (command key and comma) and turn off "Open files with safe extentions". If you do not, things you download can be automatically opened. Which is just annoying.
4) Pick a good short name. The short name is going to be used for your 'home' directory. This is where you store all of your personal files. This is a pain in the ass to change, so pick something you want to keep forever. I made the mistake the first time of letting it use my full name. That was a pain.
5) Create a applications folder inside your Users/username folder. This is a great way to test apps before you deploy them for all users to use. If the program is not secure you only compromise your users files, not the entire system. If you like the program you can then just install it in the normal system applications folder. Installing and removing apps is very easy as you will see.
6) Lean the command line and a scripting language. This will help you in the long run, I promise. Also take some time to learn applescript and automator. They are life savers.
7) Turn on the firewall. Go set it to allow by application, the firewall will ask you when you try to use a network app. Simply supply the admin accounts username/password.
8) Turn on right mouse buttons and two finger tapping. Right click is awesome, so don't forget to turn it on.
10) Set the control panel to lock and unlock per panel. This is more secure, if you forget to lock a panel, only that panel will be insecure not your entire control panel.
9) Get a firewire/usb drive and setup Time Machine. This is a great backup app.
a) Exclude folders with large amounts of data that you do not care if you lose.
b) I prefer a entire system back up so I can restore a working system from time machine, but others exclude everything but their Users folders.
That is all I can think of at the moment, I'm going on a month with my mac and those are the tips I have for starting out.