My Startup List
I just bought my 2012 13" Macbook Air after being Mac-less since 2008 (I've been surviving with a 10.1" netbook with an Atom N270 processor

). Here's the goodies I put on it with an explanation as to why:
CCleaner - I've used this extensively on Windows to keep the temp files from building up. You'd be surprised how much space you can free up if you run this every once in a while. It also allows us to remove applications from our Macs without leaving straggling files behind.
Evernote - Evernote is a fantastic app that I use on my iPhone to record all sorts of notes and thoughts. Now that I have it on my Mac, anything I record gets sent to iCloud (or Dropbox) and is available from all my devices.
The Unarchiver - A must-have, easy-to-use, no-frills application that will fulfill all your compression needs.
Skitch - Honestly, I haven't used this at all yet, but I've read really good reviews about how this lets you grab screenshots or images and modify them. It's no Photoshop but it's free, so I thought I'd check it out.
Skype - My method of keeping in touch with my family and friends when one of us has gone international. Why bother paying the long-distance fees when you can chat through the web (you can use the iPhone app over 3G, btw) and even have video conferencing.
Caffine - In periods of inactivity, the Mac's screen dims. Unfortunately, this happens even when you're watching videos. To combat this issue, Caffine puts a coffee cup in your menu bar. Fill it up with a click and you'll be undisturbed through the rest of your film.
Alfred - The new "Quicksilver", from what I'm told. Basically, Alfred will take inventory of everything on your computer. Assign it to a hotkey and with the click of a couple buttons, you can start typing anything and it'll pull up whatever it is you're looking for. You can even search text within documents!
Moom - My absolute favorite app thus far. It's very passive and enables windows-management. There are a lot to pick from but Moom seemed to have the cleanest interface. This app enables not only the snap-to-sides functionality that you see in Windows 7 but also gives you a bunch of pre-set locations, allows you to customize your own locations, and even a grid to pinpoint a specific spot.
Day One - I thought I'd start journaling and this app's interface is just bliss.
Adium - The best IM client for the Mac. It's very simple and just works.
Steam - Gotta have the gaming.
VLC - Allows you to watch almost any video. If you're coming from Windows, then you already know how this works.
I hope this list is helpful and a good way to get off the ground. What I recommend is to just open up the MacApp Store and look through the list of the top free apps. I hope you enjoy your Mac!
For example vlc is something I would most likely think of installing for movies(never used imovie before so I might not have to install vlc after all).
iMove is a video editor, not a video player. VLC is still your best player.